找到攜帶的最大重量子集

一個人的物品重量低於其重量。找到攜帶的最大重量子集

[10,10,12,15,16,20,45,65,120,140,150,178,198,200,210,233,298,306,307,310,375,400,420 ，411，501，550，662，690，720，731，780，790]

他可以帶回家的最大重量是3公斤（3000克）。他希望儘可能多地注意。

注意我嘗試了回溯算法，但它給了我等於我正在尋找的總和的子集，但是在我無法找到相等匹配總和的情況下，那麼它失敗了。我想找到接近總和的子集。

來源

2015-02-11 Venkata Krishna

爲什麼不記錄當前最佳結果，如果當前值和目標之間的差值小於以前的最佳結果，則遍歷並更新該值？ – 2015-02-11 12:20:17

這是subset sum problem是solveable在Dynamic Programming - 這基本上是一種有效的實現您的回溯一個，按照下面的遞推公式：

D(0,n) = True 
D(x,0) = False | x > 0 
D(x,n) = D(x-arr[i], n-1)   OR  D(x,n-1) 
      ^       ^
     item i is in subset   item i is not in subset

通過採用自下而上的動態規劃（創建一個矩陣並從低到高填充）或自上而下的動態規劃（記憶每個結果並檢查它是否已在遞歸之前計算），這可在O(n*W)中解決，其中n是元素的數量，W是子集的大小（ 3000你的情況）。

如果您運行自下而上的DP，則最大值爲x，因此D(x,n) = True是可承載的最大權重。爲了找到實際項目，應該按照表格回來，檢查在每個決策點添加了哪些項目，併產生添加的項目。返回實際集合在線程中更詳細地解釋：How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?（此線程處理揹包問題，這是您的問題的一個變體，每個項目的重量=成本）

來源

2015-02-11 12:18:15 amit

有趣的一面你回答：你有沒有任何參考，在遞歸與memoization一起被稱爲「自上而下的動態規劃」？我多年來一直在考慮這是否被認爲是動態編程，或者「動態編程」意味着根本沒有執行遞歸調用。 – Codor 2015-02-11 12:34:24

@Codor雖然它不是一個權威，但是[wikipedia page]（http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming）使用這個術語： – amit 2015-02-11 12:40:01

'自上而下的方法：這是直接失敗任何問題的遞歸表述。如果任何問題的解決方案可以使用其子問題的解決方案遞歸制定，並且如果其子問題重疊，則可以輕鬆地將解決方案存儲或存儲在表中的子問題的解決方案中。每當我們試圖解決一個新的子問題時，我們首先檢查該表是否已經解決。如果解決方案已經記錄下來，我們可以直接使用它，否則我們解決子問題並將其解決方案添加到表格中。' – amit 2015-02-11 12:40:31

使用回溯，我們可以構建這樣的解決方案，
我們將嘗試返回這是最近的，但使用這種僞碼給定的重量也降低了子集的最大重量：

func(weight_till_now,curr_pos) 
    if(weight_till_now > max_possible) return 0 
    if(curr_pos >= N) return 0 

    // Taking this weight in current subset 
    weight = max(weight_till_now,func(weight_till_now+wt[curr_pos],curr_pos+1)) 

    // Not taking in current subset 
    weight = max(weight_till_now,func(weight_till_now,curr_pos+1)) 

    return weight

調用帶有初始參數此功能將0,0給你的答案，因爲這將使每個子集，並嘗試獲得所有可能的子集權重的最大權重，如果它是大於最大可能的重量，那麼這將返回0.

來源

2015-02-11 12:53:29

找到攜帶的最大重量子集

回答

相關問題