背包代码-不适用于某些情况
背包代码-不适用于某些情况
提问于 2013-12-25 08:25:31
我的代码如下：
#include<stdio.h>
int max(int a,int b)
{
return a>b?a:b;
}
int Knapsack(int items,int weight[],int value[],int maxWeight)
{
int dp[items+1][maxWeight+1];
/* dp[i][w] represents maximum value that can be attained if the maximum weight is w and
items are chosen from 1...i */
/* dp[0][w] = 0 for all w because we have chosen 0 items */
int iter,w;
for(iter=0;iter<=maxWeight;iter++)
{
dp[0][iter]=0;
}
/* dp[i][0] = 0 for all w because maximum weight we can take is 0 */
for(iter=0;iter<=items;iter++)
{
dp[iter][0]=0;
}
for(iter=1;iter<=items;iter++)
{
for(w=0;w<=maxWeight;w=w+1)
{
dp[iter][w] = dp[iter-1][w]; /* If I do not take this item */
if(w-weight[iter] >=0)
{
/* suppose if I take this item */
dp[iter][w] = max( (dp[iter][w]) , (dp[iter-1][w-weight[iter]])+value[iter]);
}
}
}
return dp[items][maxWeight];
}
int main()
{
int items=9;
int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10};
int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87};
int iter;
int i;
int maxWeight=180;
for (i=0;i<10;i++){
value[i] = value[i]*weight[i];
}
printf("Max value attained can be %d\n",Knapsack(items,weight,value,maxWeight));
}我的背包代码在
items=12;
int weight[/*items+1*/13]={60, 20, 20, 20, 10, 20, 10, 10, 10, 20, 20, 10};
int value[/*items+1*/13]={48, 77, 46, 82, 85, 43, 49, 73, 65, 48, 47, 51};它返回了正确的输出7820。
但是它没有返回正确的输出
items=9;
int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10};
int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87};如果返回输出9730，则正确的输出应为14110。从观察来看，程序以某种方式跳过了第一个值(weight=60，value =73)。我已经检查了几次代码，但我就是找不到哪里出了问题。谁能给我解释一下原因吗？谢谢!
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-12-25 08:38:28
在您的代码中，您试图访问weight和value数组的越界索引。当iter达到9值时，weight[iter]和value[iter]成为超出界限的索引。我想，在C中，您只需获得一些超出索引访问权限的垃圾值，但在Java中，这会引发异常。将内部for循环中的代码更改为：
dp[iter][w] = dp[iter-1][w]; /* If I do not take this item */
if(w-weight[iter - 1] >=0)
{
/* suppose if I take this item */
dp[iter][w] = maximum( (dp[iter][w]) , (dp[iter-1][w-weight[iter - 1]])+value[iter - 1]);
}一切都会好起来的。
Stack Overflow用户
发布于 2013-12-25 09:14:48
int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10};
int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87};数组的长度为10，但只填充了9个条目。因此，最后一个条目被填充为0。How to initialize all members of an array to the same value?
int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10, 0};
int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87, 0};，但是您正在尝试访问算法中的索引(1到9)。
相反，尝试填充所有条目：
int weight[/*items+1*/10]={0, 60, 10, 20, 20, 20, 20, 10, 10, 10};
int value[/*items+1*/10]={0, 73, 81, 86, 72, 90, 77, 85, 70, 87};编辑：
第一种情况提供正确的输出，因为在这种情况下，第一项不包括在最优解中。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20770663
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号