[[381493]]

多重背包

對于多重背包，我在力扣上還沒發(fā)現(xiàn)對應的題目，所以這里就做一下簡單介紹，大家大概了解一下。

有N種物品和一個容量為V 的背包。第i種物品最多有Mi件可用，每件耗費的空間是Ci ，價值是Wi 。求解將哪些物品裝入背包可使這些物品的耗費的空間 總和不超過背包容量，且價值總和最大。

多重背包和01背包是非常像的， 為什么和01背包像呢?

每件物品最多有Mi件可用，把Mi件攤開，其實就是一個01背包問題了。

例如：

背包最大重量為10。

物品為：

問背包能背的物品最大價值是多少?

和如下情況有區(qū)別么?

毫無區(qū)別，這就轉(zhuǎn)成了一個01背包問題了，且每個物品只用一次。

這種方式來實現(xiàn)多重背包的代碼如下：

void test_multi_pack() { 
    vector<int> weight = {1, 3, 4}; 
    vector<int> value = {15, 20, 30}; 
    vector<int> nums = {2, 3, 2}; 
    int bagWeight = 10; 
    for (int i = 0; i < nums.size(); i++) { 
        while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展開 
            weight.push_back(weight[i]); 
            value.push_back(value[i]); 
            nums[i]--; 
        } 
    } 
 
    vector<int> dp(bagWeight + 1, 0); 
    for(int i = 0; i < weight.size(); i++) { // 遍歷物品 
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量 
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 
        } 
        for (int j = 0; j <= bagWeight; j++) { 
            cout << dp[j] << " "; 
        } 
        cout << endl; 
    } 
    cout << dp[bagWeight] << endl; 
 
} 
int main() { 
    test_multi_pack(); 
} 

• 時間復雜度：O(m * n * k) m：物品種類個數(shù)，n背包容量，k單類物品數(shù)量

也有另一種實現(xiàn)方式，就是把每種商品遍歷的個數(shù)放在01背包里面在遍歷一遍。

代碼如下：(詳看注釋)

void test_multi_pack() { 
    vector<int> weight = {1, 3, 4}; 
    vector<int> value = {15, 20, 30}; 
    vector<int> nums = {2, 3, 2}; 
    int bagWeight = 10; 
    vector<int> dp(bagWeight + 1, 0); 
 
 
    for(int i = 0; i < weight.size(); i++) { // 遍歷物品 
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量 
            // 以上為01背包，然后加一個遍歷個數(shù) 
            for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍歷個數(shù) 
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]); 
            } 
        } 
        // 打印一下dp數(shù)組 
        for (int j = 0; j <= bagWeight; j++) { 
            cout << dp[j] << " "; 
        } 
        cout << endl; 
    } 
    cout << dp[bagWeight] << endl;  
} 
int main() { 
    test_multi_pack(); 
} 

• 時間復雜度：O(m * n * k) m：物品種類個數(shù)，n背包容量，k單類物品數(shù)量

從代碼里可以看出是01背包里面在加一個for循環(huán)遍歷一個每種商品的數(shù)量。和01背包還是如出一轍的。

當然還有那種二進制優(yōu)化的方法，其實就是把每種物品的數(shù)量，打包成一個個獨立的包。

和以上在循環(huán)遍歷上有所不同，因為是分拆為各個包最后可以組成一個完整背包，具體原理我就不做過多解釋了，大家了解一下就行，面試的話基本不會考完這個深度了，感興趣可以自己深入研究一波。

總結(jié)

多重背包在面試中基本不會出現(xiàn)，力扣上也沒有對應的題目，大家對多重背包的掌握程度知道它是一種01背包，并能在01背包的基礎上寫出對應代碼就可以了。

至于背包九講里面還有混合背包，二維費用背包，分組背包等等這些，大家感興趣可以自己去學習學習，這里也不做介紹了，面試也不會考。

本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。