逆揹包問題

我試圖解決下一個任務：給定一組項目，每個項目都有一個權重和一個值，確定給定總值的揹包最小承載能力。逆揹包問題

對於實例輸入：

item1: w = 3.4, v = 3 
item2: w = 0.4, v = 1 
total value = 7

輸出：

我們應該採取：

item1 x0, item2 x7

而且

minimal capacity = 0 * 3.4 + 0.4 * 7 = 2.8 
total value = 7

什麼遞推公式我應該用於使用動態編程的通用算法？任何人都可以通過微小的輸入數據顯示解決這個問題的例子

P.S.對不起我的英語不好。

來源

2011-10-29 yuyoyuppe

這看起來像一個家庭作業問題。如果是這樣，你應該這樣標記它。另外，您需要在解決此問題時展示一些努力。請告訴我們您嘗試過的方法以及遇到的問題。 –

@VaughnCato，我在網上搜索了公式或例子，但是除了「經典」揹包問題外，沒有發現任何東西。我知道我應該像F = Sum（Weighti * Counti）[i = 0..n]（n - ItemCount）和F2 = Sum（Valuei * Counti）[i = 0..n]應該> =比total_value，但我不能做公式或算法。 – yuyoyuppe

什麼是「最小承載能力」？爲什麼它不只是沒有任何項目？ – hugomg

傳統的（最大化）揹包算法應該很好。只需將max的所有匹配項替換爲min即可，您應該快要到達那裏了。另一種看待這種情況的方法是使用負面成本，因此最小化成爲最大化（但您需要特別注意空白的情況）。

來源

2011-10-29 15:56:10 hugomg

回答

相關問題