动态规划算法
## 1、动态规划算法### 1.1、算法介绍
- 动态规划(Dynamic Programming)算法的核心思想是：将**大问题划分为小问题**进行解决，从而一步步获取最优解的处理算法
- 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
- 与分治法不同的是，适合于用动态规划求解的问题，经分解得到**子问题往往不是互相独立的**。( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
- 动态规划可以通过**填表**的方式来逐步推进，得到最优解
### 1.2、算法的应用----背包问题
| 物品 | 重量 | 价值 |
| ---- | ---- | ---- |
| 吉他 | 1 | 1500 |
| 音响 | 4 | 3000 |
| 电脑 | 3 | 2000 |
一个背包最多装4kg的东西，求
- 装入物品使得背包的总价值最大，且不超出背包的容量
- 要求装入的物品**不能重复**（01背包）
PS：01背包代表一个物品只能放一次，完全背包指的是每种物品都有无限件可用
### 1.3、思路解析
> 每次遍历到的第 i 个物品，根据 w和 v来确定是否需要将该物品 放入背包中。
>
> 即对于给定的 n 个物品，设 v、w分别为第 i 个物品的价值和重量，C 为背包的容量。
>
> 再令 v 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果：
>
公式为：
```java
//表示填入表的第一行和第一列是 0，主要是为了方便表示物品和容量
(1) v=v=0;
// 当准备加入新增的商品的重量大于当前背包的容量时，就直接使用上一个单元格的装入策略（装入物品的价值）
(2) 当 w>j 时：v=v
// 当准备加入的新增的商品的容量小于等于当前背包的容量,
// 装入的方式:
(3) 当 j>=w时：v=max{v, v+v]}
//v：表示上一个装法的总价值
//v : 表示当前商品的价值
//j-w：表示还能装入多重的商品
//v] ： 表示装入i-1商品，到剩余空间j-w的总价值
```
### 1.4、代码实现
```java
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;
//用于表示物品放入背包的方式
int[][] method = new int;
//依次将物品放入背包
for(int i = 1; i<maxValue.length; i++) {
for(int j = 1; j<maxValue.length; j++) {
//如果物品的重量大于背包剩余的容量，就不放入
//i-1是因为下标是从1开始的，减一后才为0
if(weight > j) {
maxValue = maxValue;
} else {
//背包剩余的容量
int remaining = j - weight;
//如果放入该物品前的最大价值大于放入该物品后的最大价值，就不放入该物品
if(maxValue > value+maxValue) {
maxValue = maxValue;
} else {
maxValue = value+maxValue;
//存入放入方法
method = 1;
}
}
}
}
//打印放入背包的最大价值
for(int[] arr : maxValue) {
System.out.println(Arrays.toString(arr));
}
//打印价值最大的放法
//存放方法的二维数组的最大下标，从最后开始搜索存放方法
int i = method.length - 1;
int j = method.length - 1;
while(i > 0 && j > 0) {
if(method == 1) {
System.out.println("将第" + i + "个物品放入背包");
//背包剩余容量
j -= weight;
}
i--;
}
}
}
```
### 1.5、总结
- 装入物品的容量大于背包容量时，直接使用之前装入背包物品的最大价值(上一个同等重量的格子)
- 装入物品容量小于等于背包容量时，比较
- 装入该物品之前，背包物品的最大价值
- 装入该后，该物品的价值+剩余容量能放入物品的最大价值
选取较大者 我在准备KMP算法的视频，KMP算法看别人的博客或者视频，的确有点脑壳痛，希望我能讲的通俗易懂一点，哈哈，我写的代码和别人写的不一样哦{:301_978:} C/CPP好看点 sam喵喵 发表于 2021-4-7 21:02
C/CPP好看点
不会咋办...{:301_1008:} 逸帅 发表于 2021-4-7 21:19
不会咋办...
好巧，我也不会
页:
[1]