C++ 解决整数背包
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11036689/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Solving the Integer Knapsack
提问by hytriutucx
I a new to dynamic programing and have tried the integer knapsack problem here at SPOJ (http://www.spoj.pl/problems/KNAPSACK/) . However, for the given test cases my solution is not giving the correct output. I'd be thankful to you if you could suggest if the following implementation by me is correct. Please note that the variable backis for backtracking, about which I'm not sure how to do. I hope to have your help in implementing the backtracking too. Thanks.
我是动态编程的新手，并在 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;
}
Here are the correct input/output test cases:
以下是正确的输入/输出测试用例：
Input:
4 5
1 8
2 4
3 0
2 5
2 3
Output:
13
However, the output that I am getting is 17.
但是，我得到的输出是17.
采纳答案by sukunrt
This is a version of the Knapsack problem known as the 0-1 knapsack.
这是背包问题的一个版本，称为 0-1 背包。
You are making some silly mistakes in your code.
您在代码中犯了一些愚蠢的错误。
To begin with the first integer in input is the weight and the second is the value. While you are taking first as value and second as weight. Moreover you are taking n+1 values as input 0 to N inclusive.
首先输入中的第一个整数是权重，第二个是值。当您首先将价值视为价值，然后将其视为重量时。此外，您将 n+1 个值作为从 0 到 N 的输入。
Now in your algorithm, you are considering that you can take any number of copies of the items, this is not true this is a 0-1 knapsack. Read this http://en.wikipedia.org/wiki/Knapsack_problem.
现在在您的算法中，您正在考虑可以获取任意数量的物品副本，这是不正确的，这是一个 0-1 的背包。阅读此http://en.wikipedia.org/wiki/Knapsack_problem。
I came up with this algorithm and I submitted and got accepted. So this should work fine.
我想出了这个算法，然后提交并被接受。所以这应该可以正常工作。
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;
}
BTW don't dynamically allocate arrays simply use vectors
顺便说一句，不要动态分配数组，只是使用向量
vector <int> My_array(n);
回答by Godeke
There is a version of the knapsack problem documented well at https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-pin Python.
在https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p中有一个 Python版本的背包问题。
EDIT: Nevermind, I skipped the part where the first line input defines C and N. That said, your input example doesn't seem to load with the code you provided (it is looking for one more pair than would be expected due to the <= N). I expect that loop should be < N, to get 0..n-1 as items.
编辑：没关系，我跳过了第一行输入定义 C 和 N 的部分。也就是说，您的输入示例似乎没有加载您提供的代码（由于<= N)。我希望循环应该 < N，以获得 0..n-1 作为项目。
Fixing that I get a result of 134516145 printed, which is nonsensical.
修复我得到 134516145 打印的结果，这是荒谬的。
