0-1背包问题
有一个背包，他的容量为C(Capacity)。现在有n种不同的物品，编号为0...n-1,其中每一件物品的重量为w(i),价值为v(i)。问可以向背包中存入哪些物品，使得不超过背包容量的基础上，物品的总价值最大。
暴力解法
每件物品都可以放进背包，也可以不放进背包，将所有的方式进行穷举，找到最大的。
时间复杂度：O((2^n)*n)
F(n,C) 考虑将n个物品放进容量为C的背包，使其价值最大。
对应的，当我们放置考虑是否放置第i个物品打背包中有两种策略，即，放，不放；
F(i,C) = F(i-1,C) // 不放置第i个物品，考虑前i-1个物品的放置。
或者
V(i) + F(i-1,C - W(i)) // 考虑放置第i个物品到背包中，V(i)代表第i个物品的价值，W(i)代表第i个物品的重量;
//因为已经放进背包，所以背包需要减去第i个物品的重量，即，C - W(i)
// 对应的第i个物品的是否放置进背包，即，取比较上面两种方案的放置规则取最大值者。
F(i,C) = max( F(i-1,C), V(i)+F(i-1,C - W(i)) )
递归求解
/**
* 0-1背包递归求解
*
* @param w 物品重量
* @param v 物品价值
* @param c 背包容量
* @return 背包能装载的最大值
*/
public int knapsack01(int[] w, int[] v, int c) {
return bestValue(w, v, c, v.length-1);
}
/**
* 递归求解0-1背包问题
*
* @param w 物品重量
* @param v 物品价值
* @param c 背包容量
* @param index 考虑是否需要放置进背包的第index个物品
* @return 当前最优值
*/
private int bestValue(int[] w, int[] v, int c, int index) {
if (index <= 0 || c <= 0) {
return 0;
}
// 不考虑第index个物品
int res0 = bestValue(w, v, c, index - 1);
int res1;
if (w[index] <= c) {
// 考虑第index个物品
res1 = v[index] + bestValue(w, v, c - w[index], index - 1);
}
return Integer.max(res0, res1);
}
记忆化搜索
/**
* 带记忆化搜索的
* 0-1背包递归求解
*
* @param w 物品重量
* @param v 物品价值
* @param c 背包容量
* @return 背包能装载的最大值
*/
public int knapsack01(int[] w, int[] v, int c) {
int[][] memo = new int[w.length][c+1];
for (int[] ints : memo) {
Arrays.fill(ints, -1);
}
return bestValue1(w, v, c, v.length-1, memo);
}
/**
* 带记忆化搜索的
* 递归求解0-1背包问题
*
* @param w 物品重量
* @param v 物品价值
* @param c 背包容量
* @param index 考虑是否需要放置进背包的第index个物品
* @param memo 存储计算好的是否考虑将第i个物品放进背包的最优解
* @return 当前最优值
*/
private int bestValue1(int[] w, int[] v, int c, int index, int[][] memo) {
if (index <= 0 || c <= 0) {
return 0;
}
if (memo[index][c] != -1) {
return memo[index][c];
}
// 不考虑第index个物品
int res0 = bestValue1(w, v, c, index - 1, memo);
// 考虑第index个物品
int res1;
if (w[index] <= c) {
// 考虑第index个物品
res1 = v[index] + bestValue1(w, v, c - w[index], index - 1, memo);
}
memo[index][c] = Integer.max(res0, res1);
return memo[index][c];
}
动态规划
假设背包的容量为5，物品信息如下面的表格
| ID | weight | value |
|---|---|---|
| 0 | 1 | 6 |
| 1 | 2 | 10 |
| 2 | 3 | 12 |
那么，可以推导出记忆化搜索的记录，如下：
| ID\W | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 6 | 6 | 6 | 6 | 6 |
| 1 | 0 | 6 | 10 | 16 | 16 | 16 |
| 2 | 0 | 6 | 10 | 16 | 18 | 22 |
/**
* 动态规划
* 0-1背包递归求解
*
* @param w 物品重量
* @param v 物品价值
* @param c 背包容量
* @return 背包能装载的最大值
*/
public int knapsack01(int[] w, int[] v, int c) {
// 物品的数量n
int n = w.length;
// 声明一个二维数组用于记录 第[i个物品][容量为w的背包]存放物品的最大值
int[][] memo = new int[n][c+1];
for (int[] ints : memo) {
Arrays.fill(ints, -1);
}
// 先将0号物品分别放置在容量为0,1,2...c的背包中，背包能存放物品的最大值
for (int j = 0; j <= c; j++) {
memo[0][j] = w[j] >= v[0] ? v[0] : 0;
}
// 将陆续将 1~n 号物品，放置在容量为 0~C 背包中，背包存放物品的最大值
// i 代表第i号物品
for (int i = 1; i < n; i++) {
// j 代表背包的容量
for (int j = 0; j <= c; j++) {
// 尝试将第i号物品放置进背包，背包的最大容量
int res0 = w[i] <= j ? v[i] + memo[i - 1][j - w[i]] : memo[i - 1][j];
// 忽略第i好物品，背包的最大容量
int res1 = memo[i - 1][j];
// 比较两种放置方式，取最大值
memo[i][j] = Integer.max(res0, res1);
}
}
return memo[n - 1][c];
}
优化
0-1背包的状态转移方程
F(i,c) = max( F((i-1) , c) , v(i) + F( i-1 , c - w(i) ) )
第 i 行的元素只依赖于第 i - 1 行元素，理论上，只需要保持两行元素即可，不需要保存 n 行元素。
/**
* 动态规划
* 0-1背包递归求解
*
* @param w 物品重量
* @param v 物品价值
* @param c 背包容量
* @return 背包能装载的最大值
*/
public int knapsack01Plus(int[] w, int[] v, int c) {
// 物品的数量n
int n = w.length;
// 声明一个二维数组用于记录 第[i个物品][容量为w的背包]存放物品的最大值
int[][] memo = new int[2][c + 1];
for (int[] ints : memo) {
Arrays.fill(ints, -1);
}
// 先将0号物品分别放置在容量为0,1,2...c的背包中，背包能存放物品的最大值
for (int j = 0; j <= c; j++) {
memo[0][j] = w[j] >= v[0] ? v[0] : 0;
}
// 将陆续将 1~n 号物品，放置在容量为 0~C 背包中，背包存放物品的最大值
// i 代表第i号物品
for (int i = 1; i < n; i++) {
// j 代表背包的容量
for (int j = 0; j <= c; j++) {
// 尝试将第i号物品放置进背包，背包的最大容量
int res0 = w[i] <= j ? v[i] + memo[(i - 1) % 2][j - w[i]] : memo[(i - 1) % 2][j];
// 忽略第i好物品，背包的最大容量
int res1 = memo[(i - 1) % 2][j];
// 比较两种放置方式，取最大值
memo[i % 2][j] = Integer.max(res0, res1);
}
}
return memo[(n - 1) % 2][c];
}
优化
如果细心的小伙伴可能会看到，其实我们在计算 memo[i][j] 的时候，只依赖上一次结果中的memo[i-1][<j]的元素，所以我们可以调换计算的顺序，即，从 memo[i][0]-->memo[i][c] 改为 memo[i][c]-->memo[i][0],这样，我们就可以在一行中不断复用数组的单元格使用一维数组解决背包算法了。
/**
* 动态规划
* 0-1背包递归求解
*
* @param w 物品重量
* @param v 物品价值
* @param c 背包容量
* @return 背包能装载的最大值
*/
public int knapsack01Plus(int[] w, int[] v, int c) {
// 物品的数量n
int n = w.length;
// 声明一个二维数组用于记录 第[i个物品][容量为w的背包]存放物品的最大值
int[] memo = new int[c + 1];
Arrays.fill(memo, -1);
// 先将0号物品分别放置在容量为0,1,2...c的背包中，背包能存放物品的最大值
for (int j = 0; j <= c; j++) {
memo[j] = w[j] >= v[0] ? v[0] : 0;
}
// 将陆续将 1~n 号物品，放置在容量为 0~C 背包中，背包存放物品的最大值
// i 代表第i号物品
for (int i = 1; i < n; i++) {
// j 代表背包的容量
for (int j = c; j >= w[i]; j--) {
// 尝试将第i号物品放置进背包，背包的最大容量
memo[j] = Integer.max(v[i] + memo[j - w[i]], memo[j]);
}
}
return memo[c];
}
0-1 背包的变种
- 假设每个物品可以无限使用
思路
虽然每个物品可以无限使用，但是背包的容量有限，所以，每个物品的使用还是有最大限度的，所以我们可以将无限转换成有限的背包问题。 - 多维费用背包
背包和物品都有对应的体积和容量。要同时满足这两个约束条件达到背包能装载物品的价值最大化。
思路
三维数组 - 物品互斥约束，物品依赖约束
网友评论