(完整)贪心算法0-1背包问题(算法实验代码)

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《(完整)贪心算法0-1背包问题(算法实验代码)》，欢迎阅读！

(完整)贪心算法0-1背包问题(算法实验代码)

实验三、0—1背包问题（贪心算法）



实验代码：

＃include〉

int max（int a，int b） ｛

if(a〉b） return a； else

return b； }

void Knapsack(int *v，int ＊w，int *x,int c,int n, int m[8][100］） {

int i，j；

for(j=0；j〈c；j++) ｛

if（j〈w［n]） m［n][j]=0;

else m[n］[j]=v［n]; }

for(i=n—1；i〉=1;i-—） ｛

for（j=w［i]；j〈=c;j++）

m[i]［j]=max（m[i+1］[j]，m[i+1]［j—w[i］]+v［i］)； } for(i=1；i；i++) ｛

if(m[i］[c]==m[i+1]［c]） x［i］=0; else

{x[i］=1； c=c-w［i];} }

x［n］=(m［n］［c])？1：0; return； }



int main（） ｛

int i=0； int n=7；

int w［］=｛0，2,3，5，7,1，4，1}; int v［］=｛0，10,5,15，7,6，18，3}； int x［］=｛0，0,0，0，0,0，0,0}； printf(”物品总数为：7\n"）；

1 / 2




(完整)贪心算法0-1背包问题(算法实验代码)

printf("物品重量和价值分别为:\n”)； printf（"\n重量 价值 \n”）; for （i=1；i〈=n;i++)

printf(”%d ％d \n",w［i],v［i])； int m=15；

int array[8]［100］=｛0｝； Knapsack(v,w，x，m,7,array)；

printf（”背包能装的最大价值为： %d\n”,array［1][m]); printf("贪心算法的解为: ”)； for(i=1；i〈=n;i++) {

if(i==1)

printf(”%d",x[i])； else

printf(” ％d”，x[i]）; ｝

printf("\n"); return 0; ｝



测试截图为：



2 / 2

本文来源：https://www.wddqxz.cn/1cab33100b75f46527d3240c844769eae109a36a.html