[[420643]]

01故事起源

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

02問題解析

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

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

很容易可以想到，盡量放重量小且單價高的物品，但怎么對問題進行一個嚴謹的建模呢，繼續往下分析。

03分析

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

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

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

04小問題過度大問題

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

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

但它能裝入的價值卻不能簡單的直接分解為2個小背包，因為物品只有一個，這會導致物品重復。

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

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

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

05逆向思維

假設下面就是最終的最優解選擇的物品。

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

06算法建模

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

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

• 裝不下第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個物品遞推就行了呢，因為只需要有一種情況能得到最優解就夠了，并不需要把前面的所有劃分都枚舉出來。這其實就相當于把i個物品劃分成i-1個物品和1個物品時的情況。前面的子問題也已經包含在當前的解中了。

代碼實現

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總結

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

本文原創作者：小K，一個思維獨特的寫手。