贪心算法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 {
if(j 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 {
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};
1 / 2
printf("物品总数为：7\n");
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/0735ee4a2e3f5727a5e9620f.html