给定一个整数数组，找到最接近 K 的子集和

Question

我知道这是一个背包问题，其中权重和值相等，但我认为我在编码逻辑上犯了一个错误，因为即使对于数组中元素数量的问题，它也需要很长时间才能完成(N) 为 50 并且所需的最大金额 (M) 4500.

为了说明问题，给定一个包含N个正整数和一个正整数M的数组，数组元素只能使用一次。我们必须找到这个数组的一个子集（不一定是连续的），使得总和最接近 M 但 不超过它。

这是我使用动态规划的尝试：

int M, N, price[100];
int memo[5000][100];

int dp(int left, int g)
{
    if (left < 0)
        return -10000000;

    if (g == N)
        return M - left;

    if (memo[left][g] != -1)
        return memo[left][g];

    int ans = -1;

    ans = max(ans, dp(left - price[g], g + 1));
    ans = max(ans, dp(left, g + 1));
    //cout<<g<<ln;
    return memo[left][g] = ans;
}

void solve()
{

    cin >> M >> N;

    forn(i, N)
    {
        cin >> price[i];
    }
    int score;
    memset(memo, -1, sizeof memo);
    score = dp(M, 0);
    //print_dp(M,0);

    if (score < 0)
        cout << "NO SOLUTION";
    else
        cout << score << ln;
}

int main(){
    solve();
    return 0;
}

那么我的代码中是否有任何可能的优化可以帮助我降低复杂性，因为这甚至不是最大的测试用例，有一个 M = 10^9 的测试用例。还有我如何跟踪解决方案的实际子集，因为在这里我只是返回最终的最大可能总和。任何指导将不胜感激！谢谢

Answer 1

考虑下一个代码 (ideone)。

对于每个价格 (p)，它检查 memo 数组的所有单元格并标记单元格 j 是否可以将值 j 与 [=11= 组合] 和一些先前的总和 j-p。它还会更新 jmax - 最大可能总和，并作为结果更新 returns。对于数据集M=9 N=4 {2 3 5 11}，它给出8 数组项的总和(<=9)。

#include <iostream>
#include <cstring>
using namespace std;
int M, N, p;
int memo[5000];

int solve()
{

    cin >> M >> N;
    int i, j, jmax = 0;

    memset(memo, 0, sizeof(memo));
    memo[0] = 1;
    for(i = 0; i < N; i++) {
        cin >> p;
        for(j=M; j>=p; j--){
            if(memo[j-p]) {
               memo[j]=1;
               if(j>jmax)
                 jmax = j;
            }
        }
    }
    return jmax;
}

int main(){
    std::cout<<solve();
    return 0;
}

给定一个整数数组，找到最接近 K 的子集和

Given an array of integers, find the subset sum closest to K

algorithm

subset

knapsack-problem

dynamic-programming

subset-sum