揹包真的很簡單

作者 | 小 K

出品 | 公衆號：小 K 算法 （ID：xiaok365）

0****1

故事起源

有一個容量有限的揹包，容量爲 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，一個思維獨特的寫手。
文章首發平臺：微信公衆號【小 K 算法】。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/4pLh6_mbbItljBPBfjkKPg