01背包

1. 问题

给定背包承重W,对于n件物品(每件物品重量w_i，价值v_i),在背包的承重范围内，可以带走的物品价值总和最大是多少。

2.

对于第i件物品，有两个选择，要么装入背包，要么不装入背包。
我们用V(i, j)表示，对于i件物品，在背包承重为j的情况下，可以带走的最大物品价值总和。
V(i, j)，对于第i件物品，有如下几种情况:

1. 背包承重j<w_i（物品i的重量大于背包的总承重），这种情况下肯定放不进去。可以认为:

V(i, j)=V(i-1, j)

2. 背包承重j可以承受w_i，此时，有两种情况：

将物品i放进去V(i, j)=V(i-1, j-w_i)+v_i
物品不放进去V(i, j)=V(i-1, j)
此时V(j, j)=max(V(i-1, j-w_i)+v_i, V(i-1, j))

3.实例

i, j, v_i, w_i

if j<w_i{
    V(i, j)=V(i-1, j)
}else{
    V(i, j)=max{V(i-1, j-w_i)+v_i, V(i-1, j)}
}

物品id	物品重量	物品价值
1	2	3
2	3	4
3	4	5
4	5	6

背包承重8

物品id	物品重量	物品价值
1	2	3
2	3	4
3	4	5
4	5	6

数列物品个数 横列背包承重	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0
1(2, 3)	0	0(说明1)	3(说明2)	3(说明3)	3	3	3	3	3
2(3, 4)	0	0(说明4)	3说明(5)	4说明(6)	4	7	7	7	7
3(4, 5)	0	0	3	4	5	7	8	9	9
4(5, 6)	0	0	3	4	5	7	8	9	10

(说明1): 物品1重量为2，承重为1的背包显然放不下

j=1, w₁=2
j<w₁
V(1,1)=0

(说明2): 物品1重量为2，承重为2的背包可以放下
j=2, w₁=2
j>=w₁
V(1, 2)=max{V(1-1, 2-w₁)+v₁, V(0, 1)}=max{V(0, 2-2)+v₁, V(0, 1)}={0+3, 0}=3

(说明3):
j=3, w₁=2
j>=w₁
V(1, 3)=max(V(0, 3-2)+v₁, V(0, 3))={0+3, 0}=3

(说明4):
j=1, w₂=3
j<w₂
V(2, 1)=V(1, 1)=0

(说明5):
j=2, w₂=3
j<w₂
V(i, j)=V(i-1, j)
V(2, 2)=V(1, 2)=3

(说明6):
i=2, j=3, w₂=3
j>=w₂
V(i, j)=max{V(i-1, j-w_i)+v_i, V(i-1, j)}
V(2, 3)=max{V(1, 3-3)+4, V(1, 3)}=max(0+4, 3)=4