[[420643]]

01故事起源

有一個容量有限的背包，容量為w，以及m個待選擇的物品，每個只有一件。每個物品有一定的重量和價(jià)值，那么選擇哪些物品放入背包，可使選擇的物品總價(jià)值最大呢?

02問題解析

如果背包沒有容量限制，那肯定是把所有的物品都放入背包可使價(jià)值最大。

但現(xiàn)在背包比較小，只能選擇部分裝進(jìn)背包，比如只能放一個，那就把鉆石裝進(jìn)去。

很容易可以想到，盡量放重量小且單價(jià)高的物品，但怎么對問題進(jìn)行一個嚴(yán)謹(jǐn)?shù)慕Ｄ?，繼續(xù)往下分析。

03分析

背包有一個固定的容量，容量是1kg，或者2kg，或者3kg，其實(shí)具體的數(shù)量對問題的本質(zhì)沒有影響。

對于物品來說，也就分兩種情況，要么放入背包，要么不放。

有m個物品，那總共就有2^m種選擇方式，很明顯這個數(shù)量很大，所以也不可能直接把所有的選擇方式枚舉出來。

04小問題過度大問題

假設(shè)背包容量為1kg，那可裝入的最大價(jià)值就是將手表裝入，其他的也裝不下。

如果有一個更大的背包，它的容量可以看成是2個小容量的背包的總和。

但它能裝入的價(jià)值卻不能簡單的直接分解為2個小背包，因?yàn)槲锲分挥幸粋€，這會導(dǎo)致物品重復(fù)。

所以對物品也再進(jìn)行一次劃分，m個物品可以分解為m1+m2個，同時背包容量也分解為w1+w2。

再看上面左右兩邊，和原來的問題還是一樣的，本質(zhì)不變，只是變成了數(shù)據(jù)規(guī)模更小的一個子問題。如果有了子問題的答案，那是不是就可以組合成更大規(guī)模的答案了呢?

我猜這里肯定有同學(xué)會說，這樣分解的小問題一定能得到最終大問題的最優(yōu)解嗎?我們來嘗試證明一下。

05逆向思維

假設(shè)下面就是最終的最優(yōu)解選擇的物品。

如果從某個位置砍一刀分開，保證w1和w2能裝下自己這邊的最終選擇物品，那最優(yōu)解也就被分成了兩個小規(guī)模問題的最優(yōu)解。這也說明如果枚舉了所有小規(guī)模最優(yōu)解的組合方式，也一定能得到大規(guī)模的最優(yōu)解。

06算法建模

根據(jù)上面的分析，現(xiàn)在問題就變得簡單了，直接按物品和重量拆分小問題，通過小問題遞推出大問題就行了。

設(shè)f[i][j]表示前i個物品背包容量為j時，能選擇的最大價(jià)值。w[i]表示第i個物品的重量，v[i]表示第i個物品的價(jià)值。

• 裝不下第i個物品，則f[i][j]=f[i-1][j]
• 能裝下第i個物品，則f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i])

那為什么只需要從前i-1個物品遞推就行了呢，因?yàn)橹恍枰幸环N情況能得到最優(yōu)解就夠了，并不需要把前面的所有劃分都枚舉出來。這其實(shí)就相當(dāng)于把i個物品劃分成i-1個物品和1個物品時的情況。前面的子問題也已經(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é)

背包在動態(tài)規(guī)劃中是一個非常重要的系列，涉及的類型和變種也非常的多，今天講的01背包是最基本的一種，不過真正理解了01背包，對后續(xù)其它的背包也才能更好的掌握。

本文原創(chuàng)作者：小K，一個思維獨(dú)特的寫手。