gpt4 book ai didi

c - 背包代码 - 在某些情况下不起作用

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:07:27 25 4
gpt4 key购买 nike

我的代码如下:

    #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。根据观察,程序以某种方式跳过了第一个值(权重=60,值=73)。我已经多次检查代码,但就是找不到问题所在。有人可以向我解释为什么吗?谢谢!

最佳答案

在您的代码中,您试图访问 weightvalue 数组的越界索引。当 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]);
}

它会正常工作。

关于c - 背包代码 - 在某些情况下不起作用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20770663/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com