背包问题（基础版本：0-1背包）
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
基础背包
题目描述：有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。 可以压缩空间，f[v]=max{f[v],f[v-w[i]]+v[i]} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”，此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。
注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为f[v]。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[v-1]，这样就可以保证f[N] [V]就是最后的答案。
完全背包
题目描述：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
基本思路
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。这跟01背包问题一样有O(N*V）个状态需要求解，但求解每个状态的时间则不是常数了，求解状态f[v]的时间是O(v/c），总的复杂度是超过O(VN）的。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。
简单有效
完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c<=c[j]且w>=w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小体积高的j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。
背包问题解法
定义背包
package com.bean.bagalgorithm;
public class Bag {
/** 物品重量 */
private int weight;
/** 物品价值 */
private int value;
public Bag(
int weight,
int value) {
this.weight = weight;
this.value = value;
}
public int getWeight() {
return weight;
}
public void setWeight(
int weight) {
this.weight = weight;
}
public int getValue() {
return value;
}
public void setValue(
int value) {
this.value = value;
}
}
定义背包问题求解算法
package com.bean.bagalgorithm;
public class BagProblem {
private Bag[] bags;
private int n;
private int totalWeight;
private int[][] bestValues;
private int bestValue;
public BagProblem(Bag[] bags,
int totalWeight) {
this.bags = bags;
this.totalWeight = totalWeight;
this.n = bags.length;
if (bestValues ==
null) {
bestValues =
new int[n +
1][totalWeight +
1];
}
}
public void solve() {
for (
int j =
0; j <= totalWeight; j++) {
for (
int i =
0; i <= n; i++) {
if (i ==
0 || j ==
0) {
bestValues[i][j] =
0;
}
else {
if (j < bags[i -
1].getWeight()) {
bestValues[i][j] = bestValues[i -
1][j];
}
else {
int weight = bags[i -
1].getWeight();
int value = bags[i -
1].getValue();
bestValues[i][j] = Math.max(bestValues[i -
1][j],
value
+ bestValues[i -
1][j - weight]);
}
}
}
}
bestValue = bestValues[n][totalWeight];
}
public int getBestValue() {
return bestValue;
}
}
测试背包问题的简单代码
package com.bean.bagalgorithm;
public class BagProblemTest {
public static void main(String[] args) {
Bag[] bags =
new Bag[] {
new Bag(
2,
13),
new Bag(
1,
10),
new Bag(
3,
24),
new Bag(
2,
15),
new Bag(
4,
28),
new Bag(
5,
33),
new Bag(
3,
20),
new Bag(
1,
8) };
int totalWeight =
12;
BagProblem problem =
new BagProblem(bags, totalWeight);
problem.solve();
System.
out.println(problem.getBestValue());
System.
out.println(
"-------------------------------------");
Bag[] bagsTwo =
new Bag[] {
new Bag(
0,
0),
new Bag(
5,
10),
new Bag(
4,
40),
new Bag(
6,
50),
new Bag(
3,
30) };
int totalWeightTwo =
10;
BagProblem problemTwo =
new BagProblem(bagsTwo, totalWeightTwo);
problemTwo.solve();
System.
out.println(problemTwo.getBestValue());
System.
out.println(
"-------------------------------------");
Bag[] bagsThree =
new Bag[] {
new Bag(
3,
6),
new Bag(
4,
8),
new Bag(
6,
7),
new Bag(
2,
5),
new Bag(
5,
9) };
int totalWeightThree =
10;
BagProblem problemThree =
new BagProblem(bagsThree, totalWeightThree);
problemThree.solve();
System.
out.println(problemThree.getBestValue());
}
}
运行结果
运行结果为： 90 90 20
（完）
