给定一个背包,容量capacity。现有一堆物品,每个物品 i 的重量为 w[i] ,价值为 v[i] ,给定的数据内容如下所示。
int[] w = {2, 3, 4, 5}; //物品重量
int[] v = {3, 4, 5, 6}; //物品价值
int capacity = 8; //背包容量
要解决的问题是,如何将物品放入背包,从而获得最大的价值。(0-1背包指定了,一个物品,要么放,要么不放,不能拆开)
所以考虑到每一个物品,它都有两种决策:放或者不放
可以放入背包的前提是 w[i]<=capacity
对于每个物品,如果可以放入背包,即满足 w[i]<=capacity 条件,背包的价值就会在以下两个情况间选择较大值:
1. 当前物品放入背包:因为已经确定了当前物品 i 是要放入,因此背包容量变为 nowCapacity = 原capacity-w[i] ,总价值 = 前 i-1 个物品放入nowCapacity 背包中的价值
2. 当前物品不放入背包:总价值 = 前 i-1 个物品放入capacity背包中的价值
归结成符号语言
total = max(value[i - 1][capacity], value[i - 1][capacity - w[i]] + v[i]);
如果不满足 w[i]<=capacity ,就无法放入背包,等同于上述情况2,此时归结为符号语言
total = value[i - 1][capacity]
因此,我们用一张表来记录整个放物品的过程,行表示第 i (这个 i 是从下标1开始的)件物品,列表示背包容量
用二维数组记录这张表,dp[nums+1][capacity+1],dp[i][j] 表示背包容量为 j 时,放前 i (下标从1开始)件物品,此时获得的最大价值。
最终的结果就是 dp[nums+1][capacity+1] 的值。
整个核心代码如下:
if (j >= w[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
}
else {
dp[i][j] = dp[i - 1][j];
}
因为物品的重量、价值数组下标从0开始,所以在取数的时候要减1
完整代码
public class 背包问题 {
public static void main(String[] args) {
int[] w = {2, 3, 4, 5};
int[] v = {3, 4, 5, 6};
int capacity = 8;
int num = w.length;
int[][] dp = new int[num + 1][capacity + 1];
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= capacity; j++) {
if (j >= w[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println(dp[num][capacity]);
}
}
回溯寻找放入背包的物品
public void findWhat(int i, int j) {
if (i >= 1) {
// 第i件商品没放
if (dp[i][j] == dp[i - 1][j]) {
item[i] = 0;
findWhat(i - 1, j);
}
//第i件商品放了
else if (j - w[i - 1] >= 0 && dp[i][j] == dp[i - 1][j - w[i - 1]] + v[i - 1]) {
item[i] = 1;
findWhat(i - 1, j - w[i - 1]);
}
}
}
带有回溯物品放入情况的完整代码
public class 背包问题 {
public static int[][] dp;
public static int[] item;
public static int[] w;
public static int[] v;
public static void main(String[] args) {
w = new int[]{2, 3, 4, 5};
v = new int[]{3, 4, 5, 6};
int capacity = 8;
int num = w.length;
dp = new int[num + 1][capacity + 1];
item = new int[num + 1];
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= capacity; j++) {
if (j >= w[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println(dp[num][capacity]);
findWhat(num, capacity);
for (int i = 1; i <= num; i++) {
System.out.print(item[i] + " ");
}
System.out.println();
}
public static void findWhat(int i, int j) {
if (i >= 1) {
// 第i件商品没放
if (dp[i][j] == dp[i - 1][j]) {
item[i] = 0;
findWhat(i - 1, j);
}
//第i件商品放了
else if (j - w[i - 1] >= 0 && dp[i][j] == dp[i - 1][j - w[i - 1]] + v[i - 1]) {
item[i] = 1;
findWhat(i - 1, j - w[i - 1]);
}
}
}
}
// 输出
// 10
// 0 1 0 1
可以进行空间压缩