我正在做一個如下的編程練習：
有一個盒子和一個專案串列。
盒子有固定的尺寸。每件商品都有自己的尺寸和價格。
如果物品大小的總和小于盒子的大小，我們可以將任意數量的物品放入盒子中。（每件物品只能放置一次）。
找出可以放入盒子中且價格最高的物品組合。
box: size = 10
| item | size | price |
| ---- | ---- | ----- |
| 1 | 8 | 4 |
| 2 | 10 | 5 |
| 3 | 1 | 2 |
在這種情況下，答案將是 6，因為選擇了專案 1 和 3，價格 4 2 = 6（尺寸總和為 8，小于 10）
我的方法是執行回溯以找到所有可能的組合并記錄最高價格，但我不確定如果串列中有大量專案是否足夠有效。
有沒有更有效的方法？
uj5u.com熱心網友回復：
這正是0/1背包問題。確實，嘗試所有組合都可以解決問題，但是超過 50 個專案可能需要很長時間。
該問題是NP 完全的，但可以通過偽多項式解決。也就是說，如果盒子的總尺寸比較小，就可以有效地求解。
uj5u.com熱心網友回復：
是的，有一種方法更有效！
動態規劃 - 自底向上
方法：不是通過評估所有可能的子集來強制解決問題，而是可以為每個權重的每個專案迭代解決問題。以這個例子為例：
假設有四個i[1,2,3,4]具有相關權重w[5,3,4,2]、值v[60,50,70,30]和最大權重的專案W = 5。
我們現在將構造一個二維值陣列，它在選擇某個物品時保存最大值，某個重量，V[i][w]。
填充陣列的演算法是：
V[i][w] = max(V[i-1, w], V[i-1, w - w_i] v_i) OTHERWISE V[i-1, w]
這是做什么的？:
對于每個重量的每個專案，我們首先看是否可以在不超過重量限制的情況下選擇專案。如果不是，我們取上面那個重量的物品的價值（如果該物品也不能被選擇，則取 0）。
如果我們可以選擇專案，有趣的事情就會發生。如果是這樣，如果選擇的專案大于選擇上面的專案的值，我們選擇當前專案：
(So if V[i-1, w] < V[i-1, w - w_i] v_i)
對所有 n 個專案和 w 個權重執行此操作，您將獲得盡可能高的值。在上述示例上執行演算法時，這將是矩陣：
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 第 1 項 | 0 | 0 | 0 | 0 | 0 | 60 |
| 第 2 項 | 0 | 0 | 0 | 50 | 50 | 60 |
| 第 3 項 | 0 | 0 | 0 | 50 | 70 | 70 |
| 第 4 項 | 0 | 0 | 30 | 50 | 70 | 80 |
參見權重 5 的專案 4 列。選擇權重 5 的專案 3 給出的最大值為 70。然而，我們可以看看選擇專案 4 并查看專案 3 在該重量下的值的替代方案。在專案 3，我們可以看到我們選擇了上面專案的值為 50 的值。所以解決方案是選擇專案 4 和 2。
與蠻力方法的O(2 ^ N)相比，運行它的復雜性是O(N * W)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/369661.html
下一篇：QtC 中奇怪的執行順序