我是动态规划的新手,在 SPOJ (http://www.spoj.pl/problems/KNAPSACK/ 尝试过整数背包问题) 。但是,对于给定的测试用例,我的解决方案没有给出正确的输出。如果您能建议我的以下实现是否正确,我将不胜感激。请注意,变量 back
用于回溯,我不确定该怎么做。我希望在实现回溯方面也能得到您的帮助。谢谢。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int knapsack(int value[], int weight[], int n, int C,
vector < int >&back)
{
int *M = new int[C + 1];
int k;
int i, j, tmp, pos;
for (i = 1; i <= C; i++) {
M[i] = M[i - 1];
pos = i - 1;
for (j = 0; j < n; j++) {
k = i - weight[j];
if (k >= 0)
tmp = M[k] + value[j];
if (tmp > M[i]) {
M[i] = tmp;
}
}
back.push_back(pos);
}
int ans = M[C];
delete[]M;
return ans;
}
int main()
{
int C, N;
cin >> C >> N;
int* value = new int[N+1];
int* weight = new int[N+1];
for ( int i = 0; i <= N; i++) {
cin>>value[i]>>weight[i];
}
vector < int >back(N, 0);
cout<<knapsack(value,weight,N,C,back)<<endl;
return 0;
}
以下是正确的输入/输出测试用例:
Input:
4 5
1 8
2 4
3 0
2 5
2 3
Output:
13
但是,我得到的输出是 17
。
最佳答案
这是背包问题的一个版本,称为 0-1 背包。
您在代码中犯了一些愚蠢的错误。
首先,输入中的第一个整数是权重,第二个是值。当您将第一作为值(value),将第二作为权重时。此外,您将 n+1 个值作为输入 0 到 N(含)。
现在在你的算法中,你正在考虑你可以拿取任意数量的元素拷贝,这是不正确的,这是一个 0-1 背包。阅读此 http://en.wikipedia.org/wiki/Knapsack_problem .
我想出了这个算法,然后提交并被接受。所以这应该可以正常工作。
int M[2000][2000];
int knapsack(int value[], int weight[], int C, int n)
{
for(int i = 1; i <= C; i++){
for(int j = 0; j <n; j++){
if(j > 0){
M[j][i] = M[j-1][i];
if (weight[j] <= i)
M[j][i] = max(M[j][i], M[j-1][i-weight[j]]+value[j]);
}
else{
M[j][i] = 0;
if(weight[j] <= i)
M[j][i] = max(M[j][i], value[j]);
}
}
// cout << M[i][n-1] << endl;
}
return M[n-1][C];
}
int main()
{
int C, N;
cin >> C >> N;
// cout << C << endl;
int* value = new int[N+1];
int* weight = new int[N+1];
for ( int i = 0; i < N; i++) {
cin>>weight[i]>>value[i];
}
// vector < int >back(N, 0);
cout<<knapsack(value,weight,C,N)<<endl;
return 0;
}
顺便说一句,不要动态分配数组,只需使用 vector
vector <int> My_array(n);
关于c++ - 求解整数背包,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11036689/