重建有界 0/1 背包中的物品的算法比该线程中的一些现有代码更简单,这可能会让人们相信。这个答案旨在稍微揭开这个过程的神秘面纱,并提供一个干净、直接的实现以及一个工作示例。
该方法
从与表轴相对应的两个索引开始:一个weight
初始化为背包容量的变量和一个i
沿项目轴在 DP 查找表上向后循环的索引,在索引 1 处停止(算法使用i-1
因此在 1 处停止以避免越界使用权)。
在循环中, if T[weight][i] != T[weight][i-1]
,将 item 标记i-1
为选中,减去其权重并继续沿 item 轴向后退。
重构的时间复杂度为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
) so 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;
}
也可以看看