这里我有使用背包算法(bin packing NP-hard problem)计算最优值的代码:
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];
}
还需要显示包中包含的元素。我想创建一个数组来存放选中的元素。问题是，哪一步可以执行这个选择?还有其他更有效的方法来确定哪些物品被拿走了吗?
我希望能够知道给我最优解的项，而不仅仅是最优解的值。
可以使用矩阵中的数据来获取您从矩阵中打包的元素，而无需存储任何额外的数据。
伪代码:
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
它背后的思想是你迭代矩阵;如果重量差正好是元素的大小，那么它就在背包中。如果不是，说明物品不在背包里，那就别带了。
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);
用于重建有界0/1背包中的物品的算法比这个线程中的一些现有代码可能导致人们认为的更简单。这个答案的目的是揭开这个过程的神秘面纱，并提供一个干净，直接的实现以及一个工作示例。
的方法
从对应于表轴的两个索引开始:一个初始化为背包容量的weight变量和一个索引i，它沿着项目轴在DP查找表上向后循环，在索引1处停止(算法使用i-1，因此在1处停止可以避免越界访问)。
在循环中，如果是T[weight][i] != T[weight][i-1]，将项目i-1标记为选中，扣除其权重并沿着项目轴继续后退。
重构时间复杂度为O(length(items))。
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;
}
参见
- 在背包中打印背包中的物品
- 背包0-1路径重构(需要携带的物品)
下面是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