建站
咨詢
售后
建站咨詢
新聞中心
多重背包
創(chuàng)新互聯(lián)建站是一家專注于成都網(wǎng)站設(shè)計、網(wǎng)站建設(shè)與策劃設(shè)計,永昌網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)建站做網(wǎng)站,專注于網(wǎng)站建設(shè)十多年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:永昌等地區(qū)。永昌做網(wǎng)站價格咨詢:028-86922220
對于多重背包，我在力扣上還沒發(fā)現(xiàn)對應(yīng)的題目，所以這里就做一下簡單介紹，大家大概了解一下。
有N種物品和一個容量為V 的背包。第i種物品最多有Mi件可用，每件耗費的空間是Ci ，價值是Wi 。求解將哪些物品裝入背包可使這些物品的耗費的空間 總和不超過背包容量，且價值總和最大。
多重背包和01背包是非常像的， 為什么和01背包像呢?
每件物品最多有Mi件可用，把Mi件攤開，其實就是一個01背包問題了。
例如：
背包最大重量為10。
物品為：
| 重量 | 價值 | 數(shù)量 | |
|---|---|---|---|
| 物品0 | 1 | 15 | 2 |
| 物品1 | 3 | 20 | 3 |
| 物品2 | 4 | 30 | 2 |
問背包能背的物品最大價值是多少?
和如下情況有區(qū)別么?
| 重量 | 價值 | 數(shù)量 | |
|---|---|---|---|
| 物品0 | 1 | 15 | 1 |
| 物品0 | 1 | 15 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品2 | 4 | 30 | 1 |
| 物品2 | 4 | 30 | 1 |
毫無區(qū)別，這就轉(zhuǎn)成了一個01背包問題了，且每個物品只用一次。
這種方式來實現(xiàn)多重背包的代碼如下：
- void test_multi_pack() {
- vector
weight = {1, 3, 4}; - vector
value = {15, 20, 30}; - vector
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
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
weight = {1, 3, 4}; - vector
value = {15, 20, 30}; - vector
nums = {2, 3, 2}; - int bagWeight = 10;
- vector
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)，力扣上也沒有對應(yīng)的題目，大家對多重背包的掌握程度知道它是一種01背包，并能在01背包的基礎(chǔ)上寫出對應(yīng)代碼就可以了。
至于背包九講里面還有混合背包，二維費用背包，分組背包等等這些，大家感興趣可以自己去學習學習，這里也不做介紹了，面試也不會考。
本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。
新聞標題：動態(tài)規(guī)劃：關(guān)于多重背包，你該了解這些！
本文地址：http://www.5511xx.com/article/dpopjsd.html
