動態(tài)規(guī)劃之什么是多重背包

本篇內(nèi)容主要講解“動態(tài)規(guī)劃之什么是多重背包”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“動態(tài)規(guī)劃之什么是多重背包”吧!

多重背包

有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(); }

• 時間復(fù)雜度：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(); }

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

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

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

到此，相信大家對“動態(tài)規(guī)劃之什么是多重背包”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！