重複揹包 - 數組解決方案

Question

我想了解在課堂上給予我的揹包算法，特別是下面的僞代碼。

這是我嘗試編寫它：

//Init array 
var solution = []; 
var items = problem.items; 
var sackSize = problem.knapsack; 

solution[0] = 0; 
for(var k = 1; k <= sackSize; k++) 
{ 
    var loot = 0; 
    for(var i = 1; i <= items.length; i++) 
    { 
     if(k >= items[i].weight) 
     { 
      loot = Math.max(loot, items[i].value) 
     } 
    } 
    solution[k] = loot; 
} 

這沒有意義，我因爲if(k >= items[i].weight)總是給人一種「索引超出界限」錯誤上的最後一次迭代循環。 items數組從0開始，但i從1開始。爲什麼我們從索引1開始？我誤解了變量嗎？

我給出：

對象問題包括揹包 （problem.knapsack）的最大重量和可用項（problem.items）的陣列。 每個項目都是一個具有重量和價值屬性 （problem.items [i] .weight和problem.items [i] .value）的對象。這兩個 函數都應返回一個選定項目的數組。 返回數組中的項目也應該具有權重和值屬性。

Answer 1

你想看看items數組的每個元素。第一個元素是items[0]，最後一個元素是items[items.length-1]。

因此，你應該改變行

for (var i = 1; i <= items.length; i++) 

這樣：

for (var i = 0; i < items.length; i++) 

現在items[i].weight將是最後一次迭代有效。

那麼爲什麼僞代碼說以下？

for (i = 1; i <= n; i++) { 

好了，僞代碼是用在哪些項目是從1到n編號數學約定。您的代碼有一個不同的約定，其中項目編號從0到items.length-1。

這不是你的代碼和僞代碼之間的唯一區別。例如，您正在編寫k >= items[i].weight而不是k ≥ W[i]。此外，您使用var表示法聲明局部變量。這是因爲你的代碼是一個實際的實現。僞代碼是一種數學抽象。

僞代碼中的抽象思想是逐個查看項目，數學表達爲W[1]到W[n]。在您的代碼中，第一項是items[0]，最後一項是items[items.length-1]。您必須相應地編寫for聲明。

啊，但揹包容量呢？我們是否也必須更改該循環索引？答案是不。在這裏，我們正在處理具有不同含義的不同索引。我們不是在數組中查找項目，而是創建一個新數組，我們想要使用從0到sackSize之間的值進行索引。 solution[k]的價值是容量爲k的揹包的最佳包裝。

爲了更清楚些，我建議你聲明solution陣列像這樣：

var solution = new Array(sackSize+1); 

順便說一句，分配要求你做多的僞代碼在做什麼。僞代碼只計算您可以通過最優打包實現的總值。該任務要求您返回用於優化打包的項目數組。