你覺得背包真的很簡(jiǎn)單嗎？
01故事起源
有一個(gè)容量有限的背包，容量為w，以及m個(gè)待選擇的物品，每個(gè)只有一件。每個(gè)物品有一定的重量和價(jià)值，那么選擇哪些物品放入背包，可使選擇的物品總價(jià)值最大呢?
02問題解析
如果背包沒有容量限制，那肯定是把所有的物品都放入背包可使價(jià)值最大。
但現(xiàn)在背包比較小，只能選擇部分裝進(jìn)背包，比如只能放一個(gè)，那就把鉆石裝進(jìn)去。
很容易可以想到，盡量放重量小且單價(jià)高的物品，但怎么對(duì)問題進(jìn)行一個(gè)嚴(yán)謹(jǐn)?shù)慕Ｄ?，繼續(xù)往下分析。
03分析
背包有一個(gè)固定的容量，容量是1kg，或者2kg，或者3kg，其實(shí)具體的數(shù)量對(duì)問題的本質(zhì)沒有影響。
對(duì)于物品來(lái)說(shuō)，也就分兩種情況，要么放入背包，要么不放。
有m個(gè)物品，那總共就有2^m種選擇方式，很明顯這個(gè)數(shù)量很大，所以也不可能直接把所有的選擇方式枚舉出來(lái)。
04小問題過(guò)度大問題
假設(shè)背包容量為1kg，那可裝入的最大價(jià)值就是將手表裝入，其他的也裝不下。
如果有一個(gè)更大的背包，它的容量可以看成是2個(gè)小容量的背包的總和。
但它能裝入的價(jià)值卻不能簡(jiǎn)單的直接分解為2個(gè)小背包，因?yàn)槲锲分挥幸粋€(gè)，這會(huì)導(dǎo)致物品重復(fù)。
所以對(duì)物品也再進(jìn)行一次劃分，m個(gè)物品可以分解為m1+m2個(gè)，同時(shí)背包容量也分解為w1+w2。
再看上面左右兩邊，和原來(lái)的問題還是一樣的，本質(zhì)不變，只是變成了數(shù)據(jù)規(guī)模更小的一個(gè)子問題。如果有了子問題的答案，那是不是就可以組合成更大規(guī)模的答案了呢?
我猜這里肯定有同學(xué)會(huì)說(shuō)，這樣分解的小問題一定能得到最終大問題的最優(yōu)解嗎?我們來(lái)嘗試證明一下。
05逆向思維
假設(shè)下面就是最終的最優(yōu)解選擇的物品。
如果從某個(gè)位置砍一刀分開，保證w1和w2能裝下自己這邊的最終選擇物品，那最優(yōu)解也就被分成了兩個(gè)小規(guī)模問題的最優(yōu)解。這也說(shuō)明如果枚舉了所有小規(guī)模最優(yōu)解的組合方式，也一定能得到大規(guī)模的最優(yōu)解。
06算法建模
根據(jù)上面的分析，現(xiàn)在問題就變得簡(jiǎn)單了，直接按物品和重量拆分小問題，通過(guò)小問題遞推出大問題就行了。
設(shè)f[i][j]表示前i個(gè)物品背包容量為j時(shí)，能選擇的最大價(jià)值。w[i]表示第i個(gè)物品的重量，v[i]表示第i個(gè)物品的價(jià)值。
- 裝不下第i個(gè)物品，則f[i][j]=f[i-1][j]
- 能裝下第i個(gè)物品，則f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i])
那為什么只需要從前i-1個(gè)物品遞推就行了呢，因?yàn)橹恍枰幸环N情況能得到最優(yōu)解就夠了，并不需要把前面的所有劃分都枚舉出來(lái)。這其實(shí)就相當(dāng)于把i個(gè)物品劃分成i-1個(gè)物品和1個(gè)物品時(shí)的情況。前面的子問題也已經(jīng)包含在當(dāng)前的解中了。
代碼實(shí)現(xiàn)
- int f[101][1001], w[101], v[101];
- int n, m;
- int main() {
- cin >> m >> n;
- for (int i = 1; i <= m; ++i) {
- cin >> w[i] >> v[i];
- }
- f[0][0] = 0;
- for (int i = 1; i <= m; ++i) {
- for (int j = 0; j <= n; ++j) {
- f[i][j] = f[i - 1][j];
- if (j >= w[i]) {
- f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
- }
- }
- }
- cout << f[m][n] << endl;
- return 0;
- }
07總結(jié)
背包在動(dòng)態(tài)規(guī)劃中是一個(gè)非常重要的系列，涉及的類型和變種也非常的多，今天講的01背包是最基本的一種，不過(guò)真正理解了01背包，對(duì)后續(xù)其它的背包也才能更好的掌握。
本文原創(chuàng)作者：小K，一個(gè)思維獨(dú)特的寫手。
