c++ - 背包问题 - 找出哪些物品被拿走了
问题描述
我需要找到背包问题的每一个最优解。这是我的代码
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。我该如何解决这个问题?
下图中有表格和包装的表格解决方案
解决方案
我会使用您用来最大化价值的相同公式来查看哪些项目被选中,即
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";
}
}
}
推荐阅读
- web-hosting - 使用 DDNS 通过静态 IP 在内部服务器上托管网站
- python - model.save() 命令保存的文件在哪里
- python - 使用分隔符 / 将 2 个标签值合并为一个
- python - 为什么我的注册函数在 Python 中不起作用
- discord - 无法在不和谐机器人中同时使用命令和事件
- python - 将python中的时间范围(例如,1230-2P)转换为预先分配的垃圾箱列表?
- javascript - 无法在 React.js 中加载表
- git - 一旦冲突解决,删除/撤消将基本分支合并到功能分支中是否安全?
- templates - 带有条件的 OCP 自定义模板
- c - 替换数组的打印字符