最近看了《算法I－IV（C++語(yǔ)言描述）》中關(guān)于動(dòng)態(tài)編程求解背包問(wèn)題的部分，感覺(jué)書(shū)中描述的不是很詳細(xì)，在這里通過(guò)我個(gè)人的理解再加上書(shū)中的描述，再重溫下這一經(jīng)典問(wèn)題的動(dòng)態(tài)編程求解方法。
所謂的背包問(wèn)題，可以描述如下：一個(gè)小偷打劫一個(gè)保險(xiǎn)箱，發(fā)現(xiàn)柜子里有N類(lèi)不同大小與價(jià)值的物品，但小偷只有一個(gè)容積為M的背包來(lái)裝東西，背包問(wèn)題就是要找出一個(gè)小偷選擇所偷物品的組合，以使偷走的物品總價(jià)值最大。我們可以定義以下結(jié)構(gòu)：
struct Item {
int size; //保存物品大小
int val; //保存物品價(jià)值
};
例如有下表中的物品：
|
Index |
0 |
1 |
2 |
3 |
4 |
|
Item |
A |
B |
C |
D |
E |
|
Size |
3 |
4 |
7 |
8 |
9 |
|
Val |
4 |
5 |
10 |
11 |
13 |
上表中第一行（Index）是物品在程序中的索引號(hào)，第二行（Item）是物品的標(biāo)示，第三行（Size）是物品的大小，第四行（Val）是物品的價(jià)值，而每一列又對(duì)應(yīng)了一類(lèi)物品。假設(shè)小偷背包的容積為17，則小偷能夠拿走5個(gè)A價(jià)值為20的物品，或者1個(gè)D和1個(gè)E，價(jià)值為24的物品，等等。
為了使小偷在背包容積為cap的情況下，能夠偷走最大價(jià)值的物品，我們可以假設(shè)小偷足夠聰明，無(wú)論背包容積cap為多少，小偷總能找到最優(yōu)的組合使背包中所裝物品的價(jià)值最大。
倘若我們定義函數(shù)：
int knap( int cap );
該函數(shù)的返回值為容積為cap的背包所裝物品的最大價(jià)值。對(duì)于cap為17的背包，因?yàn)橛?類(lèi)物品，所以所裝物品的價(jià)值有以下組合：
1） 4 + knap( 17 - 3 )，即 item[0].val + knap(cap - item[0].size);
2) 5 + knap( 17 - 4 )，即 item[1].val + knap(cap - item[1].size);
3) 10 + knap( 17 - 7 )，即 item[2].val + knap(cap - item[2].size);
4) 11 + knap( 17 - 8 )，即 item[3].val + knap(cap - item[3].size);
5) 13 + knap( 17 - 9 )，即 item[4].val + knap(cap - item[4].size);
因?yàn)樾⊥狄呀?jīng)幫助我們找到了cap = cap - item[i].size的最優(yōu)組合，所以我們只需要找到item[i].val + knap(cap - item[i].size)的最大值也就完稱(chēng)了我們的任務(wù)了。
下面的程序代碼是按以上的思路編寫(xiě)的：
我么定義了一個(gè)類(lèi)型為Item的N項(xiàng)數(shù)組，對(duì)于每一個(gè)可能的項(xiàng)，我們遞歸的計(jì)算所能得到的最大值，然后挑出那些值中的最大項(xiàng)返回。
需要說(shuō)明的是，上面的代碼不應(yīng)該成為正式的代碼，如果按上面的代碼畫(huà)出每次函數(shù)調(diào)用的二叉樹(shù)圖，就會(huì)發(fā)現(xiàn)有大量重復(fù)的計(jì)算來(lái)處理同一個(gè)問(wèn)題，其結(jié)果就是耗費(fèi)指數(shù)級(jí)的時(shí)間，因而是低效的。