(完整)贪心算法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.wddqw.com/doc/1cab33100b75f46527d3240c844769eae109a36a.html