Posted on 2012-11-24 00:41
hoshelly 阅读(4117)
评论(0) 编辑 收藏 引用 所属分类:
DS && Algorithm
动态规划解决01背包问题！
代码
#include<stdio.h>
int c[10][100];/*对应每种情况的最大价值*/int w[10],p[10];int knapsack(int m,int n){ int i,j,x[10]; //w为物品重量，p为价值
for(i=1;i<n+1;i++) scanf("\n%d%d",&w[i],&p[i]); for(i=0;i<10;i++) for(j=0;j<100;j++) c[i][j]=0;/*初始化数组*/ for(i=1;i<n+1;i++) for(j=1;j<m+1;j++) { if(w[i]<=j) /*如果当前物品的重量小于背包所能承载的重量*/ { if(p[i]+c[i-1][j-w[i]]>c[i-1][j]) /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/ /*大于上一次选择的最佳方案则更新c[i][j]*/ c[i][j]=p[i]+c[i-1][j-w[i]]; else c[i][j]=c[i-1][j]; } else c[i][j]=c[i-1][j]; } printf("\n"); int contain = m; for(int i=n;i>0;--i) { if(c[i][contain] == c[i-1][contain])//未放入第i个物品，contain表示当前背包的承受重量
x[i-1] = 0; //考虑：f[i][j] = max{ f[i-1][j] 和 f[i-1][j - w[i]] + v[i] }, if ( f[i][j] == f[i-1][j] )
else //则说明物品i未放入；否则物品i 放入了背包中，最大承重量也相应减去w[i]
{ x[i-1] = 1; contain -= w[i]; // 放上了第i个物品，当前背包的重量要减去相应的物品i的重量，回溯
} } for(i=0;i<n;i++) { printf("%d ",x[i]); //1表示放入，0表示未放入
} printf("\n"); return(c[n][m]);}int main() { int m,n,i,j; scanf("%d %d",&m,&n); printf("Input the weight and value:\n"); printf("%d\n",knapsack(m,n)); return 0;}//测试数据：5 4
//2 12
//1 10
//3 20
//2 15
//结果：1 1 0 1 最大价值：37