最优组合之背包算法
?
背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。这个问题涉及到了两个条件：一是物品总的大小小于或等于背包的大小，二是物品总的价值要尽量大。
如果我们用子问题定义状态来描述的话可以这样解释：
用f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。用公式表示:
? ? ? ? ? ? ? ? ? ? ? ?f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}或?f[v]=max{f[v],f[v-c[i]]+w[i]}
? ? 具体的解释可以理解为将前i件物品放入容量为v的背包中，现只考虑第i件物品的策略（放或不放），那么就可以转化为一个只涉及前i-1件物品和第i件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。（v表示背包的最大容量，c[i]表示第i件物品的大小，w[i]表示第i件物品的价值）
算法如下：
?
????}???
程序运行的过程如下：
?
i=0时，放入李子
背包负重
1
2
3
4
5
6
7
8
s
－
－
－
4
5
6
7
8
p
－
－
－
0
1
2
3
4
value
0
0
0
4500
4500
4500
4500
9000
item
－
－
－
0
0
0
0
0
i=1时，放入蘋果
背包负重
1
2
3
4
5
6
7
8
s
－
－
－
－
5
6
7
8
p
－
－
－
－
0
1
2
3
value
0
0
0
4500
5700
5700
5700
9000
item
－
－
－
0
1
1
1
0
i=2时，放入橘子
背包负重
1
2
3
4
5
6
7
8
s
－
2
3
4
5
6
7
8
p
－
0
1
2
3
4
5
6
value
0
2250
2250
4500
5700
6750
7950
9000
item
－
2
2
0
1
2
2
0
i=3时，放入草莓
背包负重
1
2
3
4
5
6
7
8
s
1
2
3
4
5
6
7
8
p
0
1
2
3
4
5
6
7
value
1100
2250
3350
4500
5700
6800
7950
9050
item
3
2
3
0
1
3
2
3
i=4时，放入甜瓜
背包负重
1
2
3
4
5
6
7
8
s
－
－
－
－
－
6
7
8
p
－
－
－
－
－
0
1
2
value
1100
2250
3350
4500
5700
6800
7950
9050
item
3
2
3
0
1
3
2
3
?
? ? 由最后一个表格可以知道，在背包负重8的时候，最多得到价值9050的水果，这个时候可以得到装入的水果是3号水果草莓，那么剩下的（8-1=7）个大小空间，可以知到为2号水果也就是橘子，同理下一步可以知道放入的水果是1号水果苹果。此时获得的最优解的价值就是9050，放入的水果是草莓、橘子和苹果。
更多信息请查看?java进阶网?http://www.javady.com
