js實現01背包問題

source 發布于2019-08-21 10:56 / 1079人閱讀

摘要：背包是動態規劃中比較簡單的一個問題，其中的關鍵在于找到狀態轉換方程。表示四個物品放入大小為的背包中的最大值。就是五種商品放入容量為的背包中的最大價值，這正好就是題目的答案。

01背包是動態規劃中比較簡單的一個問題，其中的關鍵在于找到狀態轉換方程。

假設編號分別為a,b,c,d,e的五件物品，重量分別是2,2,6,5,4，價值分別是6,3,5,4,6，現在有一個承重為10的背包，如何裝入物品具有最大價值？

思路分析

首先假設有一個國王且手下有大臣A和大臣B，聰明的國王將這個問題分為放入物品a和不放入物品a兩種情況。然后國王告訴大臣A假如已經放了物品a, 那么剩下b,c,d,e四件商品放入大小為8的背包中的最大價值（其中8來自于總重量10減去物品a的重量2），然后再告訴大臣B假如沒有放入物品a, 那么在b,c,d,e四件商品中放入大小為10的背包中的最大價值。

而國王只需要比較兩個大臣的答案就可以得到最終答案。大臣A采用同樣方法把任務分給手下有A1和A2兩個人，大臣B同理。依次下去，即可得到最終的答案。

以上可以看出，關鍵步驟是將問題分解為放入物品a與不放入物品a兩種情況中的最大值，并推廣的所有的物品。這也是01的由來。

用圖形表示出來就是下面這張表。

首先注意的是該表是從左下開始填的，左邊紫色列標示物品編號，并對應的有重量與價值，第一行標示背包重量。(b, 5)表示b、c、d、e四個物品放入大小為5的背包中的最大值。(a, 10)就是abcde五種商品放入容量為10的背包中的最大價值，這正好就是題目的答案。

現在我們開始學怎么填這張表，先隨便挑一個表格(a，9)，此時背包容量為9，可以選abcde五種物品，我們要找出容量的最大值，根據上述思路分為放入物品a和不放入物品a兩種情況。

情況a: 假如放入物品a, 則背包容量變為9-2=7，還剩b,c,d,e四種物品。所以該情況下的最大值 = (b,7) + 物品a的價值6，即9+6

情況b: 假如不放入物品a, 背包容量不變為9，還剩b,c,d,e四種物品。所以該情況下的最大值 = (b, 9)，即10

所以現在(a, 9) = max( (b,7)+6, b(9) ) = max(9+6，10) = 15。

同樣的步驟填滿其他的表格即可。

代碼實現

下面是方法2的js實現

function packageMaxValue(weight, value, size){
    // 省略參數合法性校驗
    let bagMatrix = []
    for(let w = 0; w <= size; w++) {
        // js不能直接創建二維數組，所以在此初始化數組
        bagMatrix[w] = []
        for (let j = 0; j < 5; j++) {
            // 背包的容量為0，那么一個東西也裝不下，此時的值肯定也是為0
            if(w === 0) {
                bagMatrix[w][j] = 0
                continue
            }
            // 背包的容量小于物品j的重量，那么就沒有上述情況a了
            if(w < weight[j]){
                bagMatrix[w][j] = bagMatrix[w][j-1] || 0
                continue
            }
            bagMatrix[w][j] = Math.max((bagMatrix[w-weight[j]][j-1] || 0) + value[j], bagMatrix[w][j-1] || 0)
        }
    }
    return bagMatrix
}
    
let weight = [4, 5, 6, 2, 2]
let value = [6, 4, 5, 3, 6]
 
console.log(packageMaxValue(weight, value, 10))

參考：
動態規劃之01背包問題（最易理解的講解）

云服務器 GPU云服務器背包問題 java背包湊錢問題背包c語言實現 php 實現背包算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/86439.html

背包問題學習筆記

摘要：狀態轉移方程背包問題的狀態轉移方程是其中即表示前件物品恰放入一個容量為的背包可以獲得的最大價值。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價值總和最大。 01背包 01背包的概念有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。從這個題目中可以看出，01背包的特點就是：每種物品僅有一件，可以選擇放或...

xiao7cn 2019-08-20 18:05 評論0 收藏0
01背包問題（動態規劃算法）

摘要：背包問題題目給定種物品和一個容量為的背包，物品的體積是，其價值為。用子問題定義狀態其狀態轉移方程是。 P01: 01背包問題題目給定 N 種物品和一個容量為 V 的背包，物品 i 的體積是 wi，其價值為 ci 。(每種物品只有一個)問：如何選擇裝入背包的物品，使得裝入背包中的物品的總價值最大？面對每個物品，我們只有選擇放入或者不放入兩種選擇，每種物品只能放入一次。我們用之前同...

tuniutech 2019-08-23 10:52 評論0 收藏0
javascript算法基礎之01背包，完全背包，多重背包實現

摘要：背包給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。 01背包給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。 const tList = [1, 2, 3, 4, 5] // 物品體積 const vList = [3, 4, 10, 7, 4] // 物品價值 const...

seanlook 2019-08-23 14:25 評論0 收藏0
經典動態規劃--01背包問題

摘要：背包問題具體例子假設現有容量的背包，另外有個物品，分別為，，。最后，就是動態規劃的思路了。而前個物體放入容量為的背包，又可以轉化成前個物體放入背包的問題。背包問題具體例子：假設現有容量10kg的背包，另外有3個物品，分別為a1，a2，a3。物品a1重量為3kg，價值為4；物品a2重量為4kg，價值為5；物品a3重量為5kg，價值為6。將哪些物品放入背包可使得背包中的總價值最大？首先...

warkiz 2019-08-19 11:06 評論0 收藏0
王者編程大賽之三 — 01背包

摘要：動態規劃概念動態規劃過程每次決策依賴于當前狀態，又隨即引起狀態的轉移。相關文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之四約瑟夫環王者編程大賽之五最短路徑首發于樊浩柏科學院服務目前每月會對搬家師傅進行評級，根據師傅的評級排名結果，我們將優先保證最優師傅的全天訂單。 showImg(https://img3.fanhaobai.com/2017/12/2017-ziro...

Cympros 2019-07-01 12:36 評論0 收藏0