如何使用背包算法找到袋子里有哪些元素[而不仅仅是袋子的价值]？

Question

这里我有使用背包算法计算最优值的代码（装箱 NP 难题）：

int Knapsack::knapsack(std::vector<Item>& items, int W)
{
    size_t n = items.size();
    std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n + 1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for ( int w = 1; w <= W; w++)
        {
            if (items[j-1].getWeight() <= w)
            {
                dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight());
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[W][n];
}

我还需要显示包中包含的元素。我想创建一个数组来放置所选元素。那么问题来了，我可以在哪一步进行这个选择呢？还有其他更有效的方法来确定哪些物品已被拿走吗？

我希望能够知道为我提供最佳解决方案的项目，而不仅仅是最佳解决方案的价值。

Answer 1

可以使用矩阵中的数据来获取从矩阵中打包的元素，而无需存储任何其他数据。

伪代码：

line <- W
i <- n
while (i > 0):
  if dp[line][i] - dp[line - weight(i)][i-1] == value(i):
      // the element 'i' is in the knapsack
      i <- i-1 // only in 0-1 knapsack
      line <- line - weight(i)
  else: 
      i <- i-1 

其背后的想法是迭代矩阵；如果重量差恰好等于元素的大小，则它在背包中。如果不是，则该物品不在背包中，不带它继续。

Answer 2

line <- W
i <- n
while (i> 0):
  if dp[line][i] - dp[line - weight(i) ][i-1] == value(i):
    the element 'i' is in the knapsack
    cw = cw - weight(i)
    i <- i-1
  else if dp[line][i] > dp[line][i-1]:
    line <- line - 1
  else: 
    i <- i-1

只要记住当您添加项目 i 时如何到达 dp[line][i]

dp[line][i] = dp[line - weight(i) ][i - 1] + value(i);

Answer 3

用于重建有界 0/1 背包中的物品的算法比该线程中的一些现有代码可能让人相信的要简单。这个答案旨在稍微揭开这个过程的神秘面纱，并提供一个干净、直接的实现以及一个有效的示例。

---

该方法

从对应于表轴的两个索引开始：初始化为背包容量的 weight 变量和沿项目轴在 DP 查找表上向后循环的索引 i ，在索引 1 处停止（该算法使用 i-1 因此在 1 处停止可以避免越界访问）。

在循环中，如果T[weight][i] != T[weight][i-1]，则将项目i-1标记为选中，扣除其权重并继续沿着项目轴向后移动。

重建的时间复杂度为O(length(items))。

下面是 Python 伪代码：

def reconstruct_taken_items(T, items, capacity):
    taken = []
    weight = capacity

    for i in range(len(items), 0, -1): # from n downto 1 (inclusive)
        if T[weight][i] != T[weight][i-1]:
            taken.append(items[i-1])
            weight -= items[i-1].weight

   return taken

---

示例

例如，考虑背包容量为 9 和这些物品：

[item(weight=1, value=2), 
 item(weight=3, value=5), 
 item(weight=4, value=8), 
 item(weight=6, value=4)]

通过获取物品 0、1 和 2，最佳值为 15。

DP 查找表

items ---->

0  1  2  3  4
--------------+
0  0  0  0  0 | 0  capacity
0  2  2  2  2 | 1     |
0  2  2  2  2 | 2     |
0  2  5  5  5 | 3     v
0  2  7  8  8 | 4
0  2  7 10 10 | 5
0  2  7 10 10 | 6
0  2  7 13 13 | 7
0  2  7 15 15 | 8
0  2  7 15 15 | 9

为此运行重建算法：

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15 <-- weight = capacity = 9
        ^   ^
        |   |
      i-1   i = length(items) = 4

在初始状态上面，T[weight][i] == T[weight][i-1] (15 == 15) 所以item[i-1] (item(weight=6, value=4)) 未被获取。递减 i 并尝试具有相同容量的剩余项目。

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15 <-- weight = 9
        ^
        |
        i = 3

这里，T[weight][i] != T[weight][i-1] (7 != 15) 所以 items[i-1]，即 items[2] 或 item(weight=4, value=8)，必须已被获取。将剩余重量减少 items[i-1].weight 或 9 - 4 = 5，然后尝试取出 item[i-1] 不在图片中。

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10 <-- weight = 5
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15
      ^
      |
      i = 2

在这种状态下，我们再次有 T[weight][i] != T[weight][i-1] (2 != 7) 所以我们必须采取items[i-1]，即 items[1] 或 item(weight=3, value=5)。将剩余重量减少 items[i-1].weight 或 5 - 3，然后移至下一个项目。

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2 <-- weight = 2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15
   ^
   |
   i = 1

在最后一步中，我们再次有 T[weight][i] != T[weight][i-1] (0 != 2) 所以我们必须有采用 items[i-1]，即 items[0] 或 item(weight=1, value=2)。将剩余权重减少 items[i-1].weight 或 2 - 1，并退出循环，因为 i == 0。

---

C++ 实现

#include <iostream>
#include <vector>

class Knapsack {
public:
    struct Item {
        const int weight;
        const int value;
    };

private:
    static std::vector<Item> reconstruct_taken_items(
        const std::vector<std::vector<int> > &T,
        const std::vector<Item> &items,
        const int capacity
    ) {
        std::vector<Item> taken;
        int weight = capacity;
    
        for (size_t i = items.size(); i > 0; i--) {
            if (T[weight][i] != T[weight][i-1]) {
                taken.emplace_back(items[i-1]);
                weight -= items[i-1].weight;
            }
        }
    
        return taken;
    }

public:
    static std::vector<Item> solve(
        const std::vector<Item> &items, 
        const int capacity
    ) {
        std::vector<std::vector<int> > T(
            capacity + 1,
            std::vector<int>(items.size() + 1, 0)
        );
        
        for (int i = 1; i <= capacity; i++) {
            for (size_t j = 1; j <= items.size(); j++) {
                const Item &item = items[j-1];

                if (item.weight > i) {
                    T[i][j] = T[i][j-1];
                }
                else {
                    T[i][j] = std::max(
                        T[i-item.weight][j-1] + item.value, 
                        T[i][j-1]
                    );
                }
            }
        }
        
        return reconstruct_taken_items(T, items, capacity);
    }
};

int main() {
    const int capacity = 9;
    const std::vector<Knapsack::Item> items = {
        {1, 2}, {3, 5}, {4, 8}, {6, 4}
    };

    for (const Knapsack::Item &item : Knapsack::solve(items, capacity)) {
        std::cout << "weight: " << item.weight 
                  << ", value: " << item.value << "\n";
    }

    return 0;
}

---

另请参阅

• 打印背包中袋子中的物品
• <一href="https://stackoverflow.com/questions/4935533/knapsack-0-1-path-reconstruction-which-items-to-take">背包0-1路径重建（取哪些物品）

Answer 4

这是 Julia 的实现：

function knapsack!{F<:Real}(
    selected::BitVector,    # whether the item is selected
    v::AbstractVector{F},   # vector of item values (bigger is better)
    w::AbstractVector{Int}, # vector of item weights (bigger is worse)
    W::Int,                 # knapsack capacity (W ≤ ∑w)
    )

    # Solves the 0-1 Knapsack Problem
    # https://en.wikipedia.org/wiki/Knapsack_problem
    # Returns the assigment vector such that
    #  the max weight ≤ W is obtained

    fill!(selected, false)

    if W ≤ 0
        return selected
    end

    n = length(w)
    @assert(n == length(v))
    @assert(all(w .> 0))

    ###########################################
    # allocate DP memory

    m = Array(F, n+1, W+1)
    for j in 0:W
        m[1, j+1] = 0.0
    end

    ###########################################
    # solve knapsack with DP

    for i in 1:n
        for j in 0:W
            if w[i] ≤ j
                m[i+1, j+1] = max(m[i, j+1], m[i, j-w[i]+1] + v[i])
            else
                m[i+1, j+1] = m[i, j+1]
            end
        end
    end

    ###########################################
    # recover the value

    line = W
    for i in n : -1 : 1
        if line - w[i] + 1 > 0 && m[i+1,line+1] - m[i, line - w[i] + 1] == v[i]
            selected[i] = true
            line -= w[i]
        end
    end

    selected
end