问题
在N件物品取出若干件放在容量为w的背包里，每件物品的体积为w1，w2,…,wn（wi为整数），与之相对应的价值为p1,p2,…pn（pi为整数）。求背包能够容纳的最大价值。
注：每件物品只有一个，要么取要么不取
思路
- 这是一个有约束条件的求最优解的类型，考虑使用动态规划。
- 状态描述：
V(i,j) 表示当容量为 j, 放入了 i 个商品的最大总价值 p(i) 表示第 i 个商品的 价值 w(i) 表示第 i 个商品的 重量 - 状态转移：
\(V(i,j) = \begin{cases}
0 & i=0 或者 j=0 \\
max \begin{cases}
V(i-1,j) & j < w(i) \\
V(i-1,j-w(i)) + p(i) & j \geq w(i) \\
\end{cases}
\end{cases}\)
注： 很明显当 i=0 或者 j=0 的时候没有物品被放入背包，所以价值为 0 当 j < w(i) 表示当前容量不能放下 i，所以价值仍为 V(i-1,j) 当 j >= w(i) 的时候，这是就要比较放入 i 和不放 i 谁的价值更高 V(i-1,j-w(i)) + p(i) 表示放入 i 其中V(i-1,j-w(i)) 表示放入 i 之前的最高价值 - 一个很关键的点，所有数据都是整数，所以 j 只能取整数，所求为 V(i,capacity)
实现
/**
* 经典的0/1背包问题
*
* @author ychost
* @date 2018-3-15
*/
public class Knapsack {
/**
* 获取背包的所装商品的总价值
*
* @param goods 商品对象，[i][0] 表示第 i 商品的重量, [i][1] 表示第 i 个商品的价值
* @param w 背包的总重量限制
* @return 背包所装商品的最大价值
*/
static int getMaxPrice(int[][] goods, int w) {
int[][] dp = new int[goods.length + 1][w + 1];
for (int j = 0; j <= w; j++) {
for (int i = 1; i <= goods.length; i++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else {
//背包的容量不能放下该商品
if (j < goods[i - 1][0]) {
dp[i][j] = dp[i - 1][j];
} else {
int weight = goods[i - 1][0];
int price = goods[i - 1][1];
//对比放下该商品和不放该商品总价值的大小
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + price);
}
}
}
}
print(dp, goods, w);
return dp[goods.length][w];
}
/**
* 打印出商品的取舍情况，0 表示舍弃，1 表示取
*
* @param dp 动态规划结果
* @param goods 商品对象
* @param w 背包总重量
*/
static void print(int[][] dp, int[][] goods, int w) {
int j = w;
int i = goods.length;
Stack<Integer> stack = new Stack<>();
while (j > 0 && i > 0) {
int weight = goods[i - 1][0];
int price = goods[i - 1][1];
//容量不足，所以该商品没有被放入，上一次的容量为 --j
if (j < weight) {
stack.push(0);
--i;
--j;
} else {
//没有放入该商品，上一次的容量还是 j
if (dp[i][j] == dp[i - 1][j]) {
stack.push(0);
--i;
//该商品被放入了，则上一次的容量为 j-weight
} else if (dp[i][j] == dp[i - 1][j - weight] + price) {
stack.push(1);
--i;
j -= weight;
} else {
throw new RuntimeException("dp 有误");
}
}
}
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
测试数据
int[] weights = {70, 73, 77, 80, 82, 87, 90, 94, 98, 106, 110, 113, 115, 118, 120};
int[] prices = {135, 139, 149, 150, 156, 163, 173, 184, 192, 201, 210, 214, 221, 229, 240};
int w = 750;
// output
// 1458