对于有界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):
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]，即
item(weight=4, value=8)。将剩余的重量减去
items[i-1].weight，即
9 - 4 = 5，然后尝试在剩下的重量范围内寻找更小的物品。请注意保留HTML标签。
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;
}
参考资料
