1、动态规划算法
1.1、算法介绍
- 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
- 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
- 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
- 动态规划可以通过填表的方式来逐步推进，得到最优解
1.2、算法的应用----背包问题
| 物品 |
重量 |
价值 |
| 吉他 |
1 |
1500 |
| 音响 |
4 |
3000 |
| 电脑 |
3 |
2000 |
一个背包最多装4kg的东西，求
1.3、思路解析
每次遍历到的第 i 个物品，根据 w[i]和 v[i]来确定是否需要将该物品 放入背包中。
即对于给定的 n 个物品，设 v[i]、w[i]分别为第 i 个物品的价值和重量，C 为背包的容量。
再令 v[i] [j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果：
公式为：
//表示填入表的第一行和第一列是 0，主要是为了方便表示物品和容量
(1) v[i][0]=v[0][j]=0;
// 当准备加入新增的商品的重量大于当前背包的容量时，就直接使用上一个单元格的装入策略（装入物品的价值）
(2) 当 w[i]>j 时：v[i][j]=v[i-1][j]
// 当准备加入的新增的商品的容量小于等于当前背包的容量,
// 装入的方式:
(3) 当 j>=w[i]时：v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
//v[i-1][j]：表示上一个装法的总价值
//v[i] : 表示当前商品的价值
//j-w[i]：表示还能装入多重的商品
//v[i-1][j-w[i]] ： 表示装入i-1商品，到剩余空间j-w[i]的总价值
1.4、代码实现
public class Demo2 {
public static void main(String[] args) {
//各个物品的重量
int[] weight = {1, 4, 3};
//各个物品的价值
int[] value = {1500, 3000, 2000};
//背包的最大容量
int maxSize = 4;
//各种方法的价值的最大值，第0行和第0列值为0，方便后续操作
int[][] maxValue = new int[value.length+1][maxSize+1];
//用于表示物品放入背包的方式
int[][] method = new int[value.length+1][maxSize+1];
//依次将物品放入背包
for(int i = 1; i<maxValue.length; i++) {
for(int j = 1; j<maxValue[0].length; j++) {
//如果物品的重量大于背包剩余的容量，就不放入
//i-1是因为下标是从1开始的，减一后才为0
if(weight[i-1] > j) {
maxValue[i][j] = maxValue[i-1][j];
} else {
//背包剩余的容量
int remaining = j - weight[i-1];
//如果放入该物品前的最大价值大于放入该物品后的最大价值，就不放入该物品
if(maxValue[i-1][j] > value[i-1]+maxValue[i-1][remaining]) {
maxValue[i][j] = maxValue[i-1][j];
} else {
maxValue[i][j] = value[i-1]+maxValue[i-1][remaining];
//存入放入方法
method[i][j] = 1;
}
}
}
}
//打印放入背包的最大价值
for(int[] arr : maxValue) {
System.out.println(Arrays.toString(arr));
}
//打印价值最大的放法
//存放方法的二维数组的最大下标，从最后开始搜索存放方法
int i = method.length - 1;
int j = method[0].length - 1;
while(i > 0 && j > 0) {
if(method[i][j] == 1) {
System.out.println("将第" + i + "个物品放入背包");
//背包剩余容量
j -= weight[i-1];
}
i--;
}
}
}
1.5、总结
| 
[复制链接]
发表于 2021-4-7 20:03
|
发表于 2021-4-7 20:04
