0/1背包问题的多个最优解

Question

具有最大容量约束的0/1背包问题可以有多个产生相同利润但具有/不具有相同容量的最优解。我们如何从dp矩阵中生成所有最优解的集合。例如,

Capacity [4, 2, 5, 2]
Value [10, 4, 10, 4]
Maximum capacity: 7
Selected: 1,2 
Total Value: 14
DP matrix:
[[0, 0, 0, 0, 10, 10, 10, 10],
[0, 0, 4, 4, 10, 10, 14, 14],
[0, 0, 4, 4, 10, 10, 14, 14],
[0, 0, 4, 4, 10, 10, 14, 14]]

这里(1,2)，(1,4)，(2,3)和(3,4)给出了相同的利润，但通常从dp矩阵的右下角元素回溯会得到(1,2)作为解。我们如何找到所有这样的组合?

Answer 1

你可以找到所有的解，但它可能变得非常低效(因为可能有指数数量的最优解)

你需要从end返回DP矩阵，然后"spawn";每次你遇到一条有效的路线，就会产生一个新的分支(基本上，在矩阵上做一个DFS，其中节点是单元，边缘是它们之间的有效过渡，同时允许重复已经访问过的节点来发现所有路径)。

伪代码:

// i, j are indices of current element
// so_far is the list holding the current valid solution
FindSolutions(i, j, so_far):
// Stop clause: Check if this is the last element added as a valid solution
if j == 0:
so_far.append(i)
yield_copy_of(so_far)
so_far.remove_last()
for next_item in range(0, i):
// This checks if you could move from next_item to current state using i
// no boundary condition here, you should probably check it
if DP[next_item][j-weights[i]] + value[i] == DP[i][j]:
so_far.append(i)
FindSolutions(next_item, j-weights[i], so_far)
so_far.remove_last()