1. 背包问题:有一个背包,容量为4磅 , 现有如下物品
物品 | 重量 | 价格 |
---|---|---|
吉他(G) | 1 | 1500 |
音响(S) | 4 | 3000 |
电脑(L) | 3 | 2000 |
1)要求达到的目标为装入的背包的总价值最大,并且重量不超出
2)要求装入的物品不能重复
2. 过程分析
动态规划的核心思想:当前的决策是基于之前的决策基础之上的。所以背包的重量不断增加,直至最大值
物品\背包重量 | 0磅 | 1磅 | 2磅 | 3磅 | 4磅 |
---|---|---|---|---|---|
吉他(1,1500) | |||||
音箱(4,3000) | |||||
电脑(3,2000) |
step1: 当背包的容量为0时,任何物品都装不了;同理,当没有任务物品时,不管背包容量多大,其实际什么也都装不了。所以实际为:
物品\背包重量 | 0磅 | 1磅 | 2磅 | 3磅 | 4磅 |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | |
吉他(1,1500) | 0 | ||||
音箱(4,3000) | 0 | ||||
电脑(3,2000) | 0 |
step2: 当物品只有吉他时,对于不同容量的背包,其实际可能装的物品只有吉他,所以:
物品\背包重量 | 0磅 | 1磅 | 2磅 | 3磅 | 4磅 |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | |
吉他(1,1500) | 0 | 吉他(1500) | 吉他(1500) | 吉他(1500) | 吉他(1500) |
音箱(4,3000) | 0 | ||||
电脑(3,2000) | 0 |
step3: 当物品有吉他和音箱时,不同容量的背包,可装的物品有:(也只有当容量为4的时候,才有必要考虑延用之前的策略,还是用替换为当前4磅的商品)
物品\背包重量 | 0磅 | 1磅 | 2磅 | 3磅 | 4磅 |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | |
吉他 (1,1500) |
0 | 吉(1500) {只有吉他可以装入} |
吉(1500) {只有吉他可以装入} |
吉(1500) {只有吉他可以装入} |
吉他(1500){只有吉他可以装入} |
音箱 (4,3000) |
0 | 吉(1500){只有吉他可以装入} | 吉(1500){只有吉他可以装入} | 吉(1500){只有吉他可以装入} | 音箱(3000) {吉他和音箱都可以装入,就需要比哪个价值更高} |
电脑(3,2000) | 0 |
step4: 当可选物品中有吉他、音箱、电脑时,对应不同容量的背包,其选择策略是:
(注:背包是4磅时,可以参考3磅的情况。延用3磅的结果,还剩1磅的容量,此时正好满足吉他,并且其总价值大于之前4磅的所有选择)
物品\背包重量 | 0磅 | 1磅 | 2磅 | 3磅 | 4磅 |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | |
吉他(1,1500) | 0 | 吉他(1500) | 吉他(1500) | 吉他(1500) | 吉他(1500) |
音箱(4,3000) | 0 | 吉他(1500) | 吉他(1500) | 吉他(1500) | 音箱(3000) |
电脑(3,2000) | 0 | 吉他(1500) | 吉他(1500) | 电脑(2000) | 电脑+吉他(2000+1500) |
动规的体现:1)({吉他,音箱,电脑},4)参考了({吉他,音箱,电脑},3);
2)({吉他,音箱,电脑},4) 对比了({吉他,音箱},4)
3. 逻辑汇总
(1) v[i][0]=v[0][j]=0; //表示 填入表 第一列和第一行是0 (2) 当w[i]> j 时:v[i][j]=v[i-1][j] // 当准备加入新增的商品(i)的容量大于 当前背包的总容量时,意味着当前的商品无论如何也装不进去,如上图中({吉他,音箱},3), 就直接使用上一个单元格的装入策略 ({吉他},3) (3) 当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} // 当准备加入的新增的商品(i)的容量小于等于当前背包的容量,说明需要考虑新增商品。 如果新增商品的价值>之前商品的价值,则用新增商品,如果加完新增商品后,还有剩余容量,则动规考虑之前的遍历情况。 // 装入的方式: v[i-1][j]:就是上一个单元格的装入的最大值,eg: ({吉他,音箱,电脑},4) 中,i-1={吉他,音箱}; v[i] : 表示当前商品的价值 eg: v[i]=v({电脑}) v[i-1][j-w[i]] : 当剩余空间=(j-w[i])时,可装入的最大价值是:v[i-1]; ——>表明当前商品i已经被装入,则需要从其他商品中考虑。eg: 第3行,{吉他,音箱,电脑}, 当电脑被装入,则需要考虑第二行中{吉他,音箱}的情况,参考的依据就是剩余的容量(j-w[i]); 当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} ; eg: v[i-1][j] 代表 ({吉他,音箱,},4) ; v[i]+v[i-1][j-w[i]]代表: v[电脑]+v[吉他,音箱][4-w[电脑]] |
---|
4. demo
public class Main1 {
public static void main(String[] args) throws UnsupportedEncodingException {
// 新建数组,保存物品的重量
int[] weight = {1, 4, 3};
// 物品的价值
int[] value = {1500, 3000, 2000};
int m = 4; // 背包的容量
int n = value.length; // 物品的个数
// v[i][j] 表示在有i个物品中,能够装入容量为j的背包中的最大物品价值之和
int[][] v = new int[n + 1][m + 1];
// 初始化第一行第一列全部为0
for (int i = 0; i < v.length; i++) {
v[i][0] = 0;
}
for (int j = 0; j < v[0].length; j++) {
v[0][j] = 0;
}
// 根据公式来动态规划处理
for (int i = 1; i < v.length; i++) { // 商品
for (int j = 1; j < v[i].length; j++) { // 背包容量
if (weight[i - 1] > j) { // 当前商品的容量大于了背包的总容量,所以延用之前的策略
v[i][j] = v[i - 1][j];
} else {
// 因为此代码中的i是从1开始的,所以value,weight数组中的下标都需要-1
v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - weight[i - 1]]);
}
System.out.print(v[i][j] + " ");
}
System.out.println();
}
}
}
5. 记录存放的商品
public class Main1 {
public static void main(String[] args) throws UnsupportedEncodingException {
// 新建数组,保存物品的重量
int[] weight = {1, 4, 3};
// 物品的价值
int[] value = {1500, 3000, 2000};
int m = 4; // 背包的容量
int n = value.length; // 物品的个数
// v[i][j] 表示在有i个物品中,能够装入容量为j的背包中的最大物品价值之和
int[][] v = new int[n + 1][m + 1];
// 初始化第一行第一列全部为0
for (int i = 0; i < v.length; i++) {
v[i][0] = 0;
}
for (int j = 0; j < v[0].length; j++) {
v[0][j] = 0;
}
// 为了记录商品存放的情况,我们定义一个二维数组
int[][] records = new int[n + 1][m + 1];
// 根据公式来动态规划处理
for (int i = 1; i < v.length; i++) { // 商品
for (int j = 1; j < v[i].length; j++) { // 背包容量
if (weight[i - 1] > j) { // 当前商品的容量大于了背包的总容量,所以延用之前的策略
v[i][j] = v[i - 1][j];
} else {
// 因为此代码中的i是从1开始的,所以value,weight数组中的下标都需要-1
// v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - weight[i - 1]]);
// 为了记录商品存放情况,改写v[i][j]
if (v[i - 1][j] > value[i - 1] + v[i - 1][j - weight[i - 1]]) {
v[i][j] = v[i - 1][j];
// 延用了之前的策略,所以不做“商品添加”的记录
} else {
v[i][j] = value[i - 1] + v[i - 1][j - weight[i - 1]];
records[i][j] = 1; // 当前有新商品添加
}
}
System.out.print(v[i][j] + " ");
}
System.out.println();
}
System.out.println("================打印存放的商品清单=======================");
int i = records.length - 1;
int j = records[0].length - 1;
while (i > 0 && j > 0) {
if (records[i][j] == 1) {
System.out.printf("第%d个商品放入\n", i);
j -= weight[i - 1];
}
i--;
}
}
}