我需要找到背包问题的每一个最优解。 这是我的代码
void knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
i=n;
int j=W;
while(i,j>0){
if(K[j][i]!=K[j][i-1]){
cout<<"Item "<<i<<" is in the bag"<<endl;
i=i-1;
j=j-wt[i-1];
}
else
i=i-1;
}
}
输入数据是:
4 6 //n W
2 1 //p1 w1
3 2 //p2 w2
3 4 //p3 w3
4 5 //p4 w4
输出应该是这样的:
1 4
2 3
我的代码的第一部分是打包袋子,效果很好,但是我试图找到哪些元素被拿走了的第二部分给出了答案:第 3 项、第 2 项、第 1 项是错误的,因为有2 种解决方案:您采用第 1 项和第 4 项或第 2 项或第 3 项。我该如何解决这个问题?
下图是包装解决方案表
最佳答案
我会使用您用于最大化值(value)的相同公式来查看选择了哪些项目,即
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1])
然后选择项目 i
否则不选择并转到上一个项目 i-1
。
也可能有超过 1 组的元素,当他们被挑选时可以产生最大值。
在这种情况下,在数组 K[W][..]
中寻找每个这样的值以获得最大值 K[W][n]
并遍历从该点开始的数组以获取选择的项目。
代码是:
void knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
cout << "\n" << "Maximum value obtained is : " << K[W][n] << "\n";
int j;
for ( j=1; j<=n; j++ ) {
if (K[W][j] == K[W][n]) {
int w = W;
int i = j;
while(i>0 && w>0){
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1]) {
cout << "Item " << i << " is in the bag" << "\n";
w = w - wt[i-1];
i--;
} else {
i--;
}
}
cout<< "\n";
}
}
}
关于c++ - 背包问题 - 找出哪些元素被拿走了,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53339606/