建站
咨詢
售后
建站咨詢
新聞中心
多重背包
創(chuàng)新互聯(lián)建站是一家專注于成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)與策劃設(shè)計(jì),永昌網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)建站做網(wǎng)站,專注于網(wǎng)站建設(shè)十多年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:永昌等地區(qū)。永昌做網(wǎng)站價(jià)格咨詢:028-86922220
對(duì)于多重背包，我在力扣上還沒(méi)發(fā)現(xiàn)對(duì)應(yīng)的題目，所以這里就做一下簡(jiǎn)單介紹，大家大概了解一下。
有N種物品和一個(gè)容量為V 的背包。第i種物品最多有Mi件可用，每件耗費(fèi)的空間是Ci ，價(jià)值是Wi 。求解將哪些物品裝入背包可使這些物品的耗費(fèi)的空間 總和不超過(guò)背包容量，且價(jià)值總和最大。
多重背包和01背包是非常像的， 為什么和01背包像呢?
每件物品最多有Mi件可用，把Mi件攤開(kāi)，其實(shí)就是一個(gè)01背包問(wèn)題了。
例如：
背包最大重量為10。
物品為：
| 重量 | 價(jià)值 | 數(shù)量 | |
|---|---|---|---|
| 物品0 | 1 | 15 | 2 |
| 物品1 | 3 | 20 | 3 |
| 物品2 | 4 | 30 | 2 |
問(wèn)背包能背的物品最大價(jià)值是多少?
和如下情況有區(qū)別么?
| 重量 | 價(jià)值 | 數(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 |
毫無(wú)區(qū)別，這就轉(zhuǎn)成了一個(gè)01背包問(wèn)題了，且每個(gè)物品只用一次。
這種方式來(lái)實(shí)現(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，把其他物品都展開(kāi)
- 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();
- }
- 時(shí)間復(fù)雜度：O(m * n * k) m：物品種類(lèi)個(gè)數(shù)，n背包容量，k單類(lèi)物品數(shù)量
也有另一種實(shí)現(xiàn)方式，就是把每種商品遍歷的個(gè)數(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背包，然后加一個(gè)遍歷個(gè)數(shù)
- for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍歷個(gè)數(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();
- }
- 時(shí)間復(fù)雜度：O(m * n * k) m：物品種類(lèi)個(gè)數(shù)，n背包容量，k單類(lèi)物品數(shù)量
從代碼里可以看出是01背包里面在加一個(gè)for循環(huán)遍歷一個(gè)每種商品的數(shù)量。和01背包還是如出一轍的。
當(dāng)然還有那種二進(jìn)制優(yōu)化的方法，其實(shí)就是把每種物品的數(shù)量，打包成一個(gè)個(gè)獨(dú)立的包。
和以上在循環(huán)遍歷上有所不同，因?yàn)槭欠植馂楦鱾€(gè)包最后可以組成一個(gè)完整背包，具體原理我就不做過(guò)多解釋了，大家了解一下就行，面試的話基本不會(huì)考完這個(gè)深度了，感興趣可以自己深入研究一波。
總結(jié)
多重背包在面試中基本不會(huì)出現(xiàn)，力扣上也沒(méi)有對(duì)應(yīng)的題目，大家對(duì)多重背包的掌握程度知道它是一種01背包，并能在01背包的基礎(chǔ)上寫(xiě)出對(duì)應(yīng)代碼就可以了。
至于背包九講里面還有混合背包，二維費(fèi)用背包，分組背包等等這些，大家感興趣可以自己去學(xué)習(xí)學(xué)習(xí)，這里也不做介紹了，面試也不會(huì)考。
本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。
網(wǎng)站名稱：動(dòng)態(tài)規(guī)劃：關(guān)于多重背包，你該了解這些！
URL網(wǎng)址：http://fisionsoft.com.cn/article/dpopjsd.html
