Posted on 2012-11-24 00:41
hoshelly 閱讀(4145)
評論(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