algorithm - 优化这个组合算法

Question

假设您得到一个数字 N，这是您的目标 数字。然后给你一系列 p 数字，你必须找到这些数字中大于 N 的最小总和，也就是说，至少超过它(或等于它)。

您可以采用元素的任意组合的任意总和。 p 可以大到 100。

我当前的算法:扫描完所有信息后，我创建了一个 100 位长的位集，并通过循环将所有整数从 0 转换为 ( 2^p)-1 进入其中，有效地以 000...000 和 111...111 之间的所有二进制数结束。

如您所知，这些向量可以解释为 p 数字的每种可能的不同组合，其中第 i 个位置的 0 表示第 i-第 th 个数字不包含在组合中，而 1 表示它包含在内。

现在，通过遍历这个位集并检查每个组合，我一定能够实现我的目标，因为我已经检查了每个可能的组合。如果所有数字相加都不足以达到目标，则无解。

实际代码:

#include <cstdlib>
#include <iostream>
#include <cmath>
#include <bitset>

using namespace std;

int main()
{
    int N, p;
    cin >> N >> p;
    int bars[p], tot = 0;
    for (int j=0;j<p;j++){
        cin >> bars[j];
        tot += bars[j];
    }
    if (tot < N) cout << "NO SOLUTION" << endl;
    else {
         int diff = 3000;
         for (int j=0;j<pow(2.0,p)-1;j++){
             tot = 0;
             bitset<100> x(j);
             for (int k=0;k<p;k++){
                 if (x[k] == 1) tot += bars[k];
             }
             if (tot == N) {
                cout << N << endl;
                break;
             }
             if (tot-N>0&&tot-N<diff) diff = tot-N;
         }
         cout << N+diff << endl;
    }
    return 0;
}

问题:由于我们最多可以有 100 个数字，因此可能的组合数量非常多，而且根本不可行。我已经能够使用这种方法解决此类问题，但它们最多包含 20 个数字，这使得计算成为可能。这让我想到必须有更好的方法来计算这个问题。

我没有使用的额外信息:问题来自于我在设计算法时没有考虑的额外信息，这些信息可能对优化算法有用。这些数据是:

• 100 ≤ N ≤ 2500
• N是10的倍数
• 5 ≤ p ≤ 100
• 每个数字都在 50 到 2500 之间
• 它们也是10的倍数

问题:我一直在考虑优化我的算法的方法，我意识到这是你可以做的最蛮力的事情，但是，我没有实现这个目标。任何人都可以帮我优化这个，这样得出的计算结果是合理的吗？这有一个时间限制，即使我忽略了这个时间限制，但我敢肯定它不会非常高。

提前致谢。

Answer 1

这目前不适用于 p 的所有必需值。除了超时，int 不会容纳 100 位。有一个 O(p) 动态规划算法可以解决这个问题，如另一个问题中所述:Linear algorithm to find minimum subset sum over a threshold