# 0-1 背包问题详解 (1)

#### 背包问题是啥

$$\sum_{j=1}^n v_j x_j$$

$$\sum_{j=1}^n w_j x_j \le W, \; x_j \in \{0, 1\}.$$

$$\sum_{j=1}^n w_j x_j \le W, \; x_j \in \{0, 1, \ldots, b_j\}.$$

#### 哪能搞法——动态规划初试

• 如果包含第 $n$ 个物品，那么这个物品就可以直接去掉了，最优解就是只有前 $n-1$ 个物品放在 $W$ 的背包中的结果；
• 如果包含第 $n$ 个物品，那背包就被它占掉了 $w_n$ ，现在的问题就是要把前 $n-1$ 个物品放在 $W – w_n$ 的背包中怎么放法了。

$$f_n(W) = \max \begin{cases} f_{n-1} (W) \\ f_{n-1} (W – w_n) + v_n \end{cases}$$

16 4
30 4
20 5
40 10
10 3

1 30 4
2 20 5
3 40 10
4 10 3

#!/usr/bin/env python3

import sys

def knapsack(v, w, limit, n):
F = [[0] * (limit + 1) for x in range(n + 1)]
for i in range(0, n):                # F[-1] is all 0.
for j in range(limit + 1):
if j >= w[i]:
F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
else:
F[i][j] = F[i - 1][j]
return F

if __name__ == "__main__":
with open(sys.argv[1] if len(sys.argv) > 1 else sys.exit(1)) as f:
v, w = zip(*[map(int, ln.split()) for ln in f.readlines()])

F = knapsack(v, w, limit, n)
print("Max value:", F[n - 1][limit])

""" Display selected items"""
y = limit
for i in range(n - 1, -1, -1):
if F[i][y] > F[i - 1][y]:
print ("item: ", i, "value:", v[i], "weight:", w[i])
y -= w[i]

Max value: 12248
Max value: 70
item:  2 value: 40 weight: 10
item:  0 value: 30 weight: 4

[0, 0, 0, 0, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 30, 30, 30, 30, 30, 50, 50, 50, 50, 50, 50, 50, 50]
[0, 0, 0, 0, 30, 30, 30, 30, 30, 50, 50, 50, 50, 50, 70, 70, 70]
[0, 0, 0, 10, 30, 30, 30, 40, 40, 50, 50, 50, 60, 60, 70, 70, 70]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


Max value: 12248
item:  13 value: 3878 weight: 9656
item:  12 value: 1513 weight: 3926
item:  7 value: 2890 weight: 7280
item:  5 value: 1022 weight: 2744
item:  2 value: 2945 weight: 7390

def knapsack(v, w, limit, n):
F = [0] * (limit + 1)
for i in range(n):
for j in range(limit, w[i], -1):
F[j] = max(F[j - w[i]] + v[i], F[j])
return F