我知道这是一个背包问题,其中权重和值相等,但我认为我在编码逻辑中犯了一个错误,因为即使对于数组中元素数量 (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 的测试用例。 另外,在解决方案的情况下,我如何跟踪实际子集,因为在这里我只是返回最终的最大可能总和。 任何指导将不胜感激! 谢谢
最佳答案
考虑下一个代码 ( ideone )。
对于每个价格 ( p
),它会检查 memo
的所有单元格数组和标记单元格j
是否可以组成值j
与 p
和一些之前的总和 j-p
。它还更新jmax
- 最大可能总和并将其作为结果返回。对于数据集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;
}
关于algorithm - 给定一个整数数组,找到最接近 K 的子集和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/66289989/