01背包問題具體例子：假設現有容量10kg的背包，另外有3個物品，分別為a1，a2，a3。物品a1重量為3kg，價值為4；物品a2重量為4kg，價值為5；物品a3重量為5kg，價值為6。將哪些物品放入背包可使得背包中的總價值最大？
這個問題有兩種解法，動態規劃和貪婪算法。本文僅涉及動態規劃。
先不套用動態規劃的具體定義，試著想，碰見這種題目，怎么解決?
首先想到的，一般是窮舉法，一個一個地試，對于數目小的例子適用，如果容量增大，物品增多，這種方法就無用武之地了。
其次，可以先把價值最大的物體放入，這已經是貪婪算法的雛形了。如果不添加某些特定條件，結果未必可行。
最后，就是動態規劃的思路了。先將原始問題一般化，欲求背包能夠獲得的總價值，即欲求前i個物體放入容量為m（kg）背包的最大價值c[i][m]——使用一個數組來存儲最大價值，當m取10，i取3時，即原始問題了。而前i個物體放入容量為m（kg）的背包，又可以轉化成前(i-1)個物體放入背包的問題。下面使用數學表達式描述它們兩者之間的具體關系。
表達式中各個符號的具體含義。
w[i] : 第i個物體的重量；
p[i] : 第i個物體的價值；
c[i][m] ： 前i個物體放入容量為m的背包的最大價值；
c[i-1][m] ： 前i-1個物體放入容量為m的背包的最大價值；
c[i-1][m-w[i]] ： 前i-1個物體放入容量為m-w[i]的背包的最大價值；
由此可得：
c[i][m]=max{c[i-1][m-w[i]]+pi , c[i-1][m]}（下圖將給出更具體的解釋）
根據上式，對物體個數及背包重量進行遞推，列出一個表格（見下表），表格來自（
http://blog.csdn.net/fg2006/article/details/6766384?reload） ，當逐步推出表中每個值的大小，那個最大價值就求出來了。推導過程中，注意一點，最好逐行而非逐列開始推導，先從編號為1的那一行，推出所有c[1][m]的值，再推編號為2的那行c[2][m]的大小。這樣便于理解。
j表示容量
i表示i個物體
思路厘清后，開始編程序，C語言代碼如下所示。
#include <stdio.h>int c[10][100]={0};void knap(int m,int n){ int i,j,w[10],p[10]; for(i=1;i<n+1;i++) scanf("%d,%d",&w[i],&p[i]); for(j=0;j<m+1;j++) for(i=0;i<n+1;i++) { if(j<w[i]) { c[i][j]=c[i-1][j]; continue; }else if(c[i-1][j-w[i]]+p[i]>c[i-1][j]) c[i][j]=c[i-1][j-w[i]]+p[i]; else c[i][j]=c[i-1][j]; } } int main(){ int m,n;int i,j; printf("input the max capacity and the number of the goods:\n"); scanf("%d,%d",&m,&n); printf("Input each one(weight and value):\n"); knap(m,n); printf("\n"); for(i=0;i<=n;i++) for(j=0;j<=m;j++) { printf("%4d",c[i][j]); if(m==j) printf("\n"); }}代碼中，紅色字體部分是自己寫的，其余的參照了這篇博客http://blog.sina.com.cn/s/blog_6dcd26b301013810.html
如果你很輕松地就突破了01背包，甚至很輕松地就理解了動態規劃，那么繼續前進，做一下這道題目(
http://acm.uestc.edu.cn/problem.php?pid=1012)。很好玩的。
小結：
感謝上面引用的兩篇博客，也感謝這兩位博主，沒有你們的博客，我恐怕對01背包問題還是半懂不懂的。
ps: 2014/5/19 更新一個遞歸解法，《算法：c語言》似乎也有一個遞歸解法，不過是錯誤的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <stdlib.h>
typedef struct _Item
{
int size;
int val;
}item;
item aitem[5] = { {3, 4}, {4, 5}, {7,10}, {8, 11}, {9, 13} };
int item_flag[5]; // 0: 未訪問， 1：
int result[5] ; // 保存中間輸出結果
int mount = 0;
int max;
void knap_rcs(int cap)
{
int j ;
for( j = 0; j < 5; j++)
{
int t = cap - aitem[j].size;
if( t >= 0 )
{
if( item_flag[j] == 0)
{
item_flag[j] = 1;
result[j] = aitem[j].size;
mount += aitem[j].val;
knap_rcs(t);
item_flag[j] = 0;
result[j] = 0;
mount -= aitem[j].val;
}
}
else // 已到遞歸終點，輸出結果
{
int i ;
for( i =0; i < 5 ; i++)
if( result[i] != 0 )
printf("size: %d\t", result[i] );
printf("\n");
printf("%d\n", mount);
if( mount > max )
max = mount;
return ;
}
}
}
int main()
{
int N;
while(scanf("%d", &N) != 0)
{
getchar();
for(int k = 0; k < 5; k++)
{
item_flag[k] = 0;
result[k] = 0;
}
max = 0;
knap_rcs(N);
printf("max value: %d\n\n", max);
}
system("pause");
return 0;
}
分類:
探索C語言
