01背包
1. 问题
给定背包承重W,对于n件物品(每件物品重量wi，价值vi),在背包的承重范围内，可以带走的物品价值总和最大是多少。
2.
对于第i件物品，有两个选择，要么装入背包，要么不装入背包。
我们用V(i, j)表示，对于i件物品，在背包承重为j的情况下，可以带走的最大物品价值总和。
V(i, j)，对于第i件物品，有如下几种情况:
1. 背包承重j<wi（物品i的重量大于背包的总承重），这种情况下肯定放不进去。可以认为:
V(i, j)=V(i-1, j)
2. 背包承重j可以承受wi，此时，有两种情况：
将物品i放进去V(i, j)=V(i-1, j-wi)+vi
物品不放进去V(i, j)=V(i-1, j)
此时V(j, j)=max(V(i-1, j-wi)+vi, V(i-1, j))
3.实例
i, j, vi, wi
if j<wi{
V(i, j)=V(i-1, j)
}else{
V(i, j)=max{V(i-1, j-wi)+vi, 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, w1=2
j<w1
V(1,1)=0
(说明2): 物品1重量为2，承重为2的背包可以放下
j=2, w1=2
j>=w1
V(1, 2)=max{V(1-1, 2-w1)+v1, V(0, 1)}=max{V(0, 2-2)+v1, V(0, 1)}={0+3, 0}=3
(说明3):
j=3, w1=2
j>=w1
V(1, 3)=max(V(0, 3-2)+v1, V(0, 3))={0+3, 0}=3
(说明4):
j=1, w2=3
j<w2
V(2, 1)=V(1, 1)=0
(说明5):
j=2, w2=3
j<w2
V(i, j)=V(i-1, j)
V(2, 2)=V(1, 2)=3
(说明6):
i=2, j=3, w2=3
j>=w2
V(i, j)=max{V(i-1, j-wi)+vi, V(i-1, j)}
V(2, 3)=max{V(1, 3-3)+4, V(1, 3)}=max(0+4, 3)=4
