优化这个组合学算法

Question

假设给你一个数字，N，这是你的目标数字。然后给你一系列p个数，你必须找到这些数中大于N的最小和，也就是说，它最小地超过了N（或者等于N）。

你可以取任意元素组合的任意和。p可以大到100。

我目前的算法：在扫描所有信息后，我创建了一个100位长的位集，并通过使用循环将从0到（2^p）-1的所有整数转换为它，有效地结束了000…000和111…111之间的所有二进制数。

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

现在，通过循环这个位集并检查每个组合，我肯定能够达到我的目标，因为我已经检查了每个可能的组合。如果所有数字加在一起都不足以达到目标，那么就没有解决方案。

实际代码：

#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)动态规划算法可以解决这个问题，正如在另一个问题中提到的:寻找超过阈值的最小子集和的线性算法