一、动态规划算法介绍
- 核心思想：将大问题分成小问题，进而一步步获取最优解的处理算法
- 与分治法类似，先解决子问题，再从子问题的解中得到问题的解
- 与分治法不同的是，适合于动态规划的问题，分解后的子问题往往不是相互独立的（即下阶段求解是建立在上个阶段的解的基础上）。
- 可通过填表的方式逐步推进
- 公式：
OPT(i) = max(选i，不选i)
二、背包问题
有一个背包，容量为4磅，现有如下物品
| 物品 | 重量 | 价格 |
|---|---|---|
| 吉他(G) | 1 | 1500 |
| 音响(S) | 4 | 3000 |
| 电脑(L) | 3 | 2000 |
要求：
- 装入物品达到总价值最大，且重量不超出
- 装入的物品不能重复
分析：
- 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是：每种物品都有无限件可用)
- 这里的问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
三、问题解决
| 物品(i)\容量(j) | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 无 | 0 | 0 | 0 | 0 | 0 |
| 吉他1500(1) | 0 | 1500 | 1500 | 1500 | 1500 |
| 音响3000(4) | 0 | 1500 | 1500 | 1500 | 3000 |
| 电脑2000(3) | 0 | 1500 | 1500 | 2000 | 3500 |
table[i][j]表示前i个物品能装入容量为j的背包的最大价值。
w[i]表示第i的物品的重量。
v[i]表示第i个物品的价值。
问题解决思路：从上到下遍历物品，先排除未被遍历的物品。如当背包容量为4的情况下，遍历到物品吉他，判断吉他的重量是否大于背包的重量，如果大于，则将table[1][4]的值置为上一个单元格的值，即table[0][4]。如果小于，比较table[0][4]和放入吉他后+剩余空间（0）的最大价值。在继续往下遍历，以此类推，最后table[maxi][4]即是要求的最大价值。
实际上，该问题的求解主要用到容量为4的这一列，其他列使用来填充剩余空间的
公式：
- 当
i=0或j=0，即table[i][0]或table[0][j]时，总价值都为0. - 当
w[i]>j,即要加入到的物品重量大于背包的总重量时，直接使用上一个单元格的策略，因为这个物品i装不下，所以物品列表有他没他都一样。 - 当
w[i]<=j，即要加入的物品重量 小于等于背包的总重量时，出现了新的决策方式：放入该物品，求出剩余的空间，在表格中寻找与剩余空间相等的背包空间，新决策方式的最大价值为，该物品的价值+剩余空间的最大价值。table[i][j] = max{ table[i-1][j] , v[i] + table[i-1][j-w[i]] }
四、代码
public class KnapsackProblem {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] w = {1, 4, 3};//物品的重量
int[] val = {1500, 3000, 2000}; //物品的价值 这里val[i] 就是前面讲的v[i]
int m = 4; //背包的容量
int n = val.length; //物品的个数
//创建二维数组，
//v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
int[][] v = new int[n+1][m+1];
//为了记录放入商品的情况，我们定一个二维数组
int[][] path = new int[n+1][m+1];
//初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
for(int i = 0; i < v.length; i++) {
v[i][0] = 0; //将第一列设置为0
}
for(int i=0; i < v[0].length; i++) {
v[0][i] = 0; //将第一行设置0
}
//根据前面得到公式来动态规划处理
for(int i = 1; i < v.length; i++) { //不处理第一行 i是从1开始的
for(int j=1; j < v[0].length; j++) {//不处理第一列, j是从1开始的
//公式
if(w[i-1]> j) { // 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
v[i][j]=v[i-1][j];
} else {
//说明:
//因为我们的i 从1开始的， 因此公式需要调整成
//v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
//v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
//为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
//把当前的情况记录到path
path[i][j] = 1;
} else {
v[i][j] = v[i - 1][j];
}
}
}
}
//输出一下v 看看目前的情况
for(int i =0; i < v.length;i++) {
for(int j = 0; j < v[i].length;j++) {
System.out.print(v[i][j] + " ");
}
System.out.println();
}
System.out.println("============================");
//输出最后我们是放入的哪些商品
//遍历path, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入
// for(int i = 0; i < path.length; i++) {
// for(int j=0; j < path[i].length; j++) {
// if(path[i][j] == 1) {
// System.out.printf("第%d个商品放入到背包\n", i);
// }
// }
// }
//动脑筋
int i = path.length - 1; //行的最大下标
int j = path[0].length - 1; //列的最大下标
while(i > 0 && j > 0 ) { //从path的最后开始找
if(path[i][j] == 1) {
System.out.printf("第%d个商品放入到背包\n", i);
j -= w[i-1]; //w[i-1]
}
i--;
}
}
}
五、题目2
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
来源：力扣（LeetCode）53题
链接：https://leetcode-cn.com/problems/maximum-subarray
思路
遍历方式 因为可以产生递推关系, 采用动态规划时, 经常通过此种遍历方式, 如 背包问题, 最大公共子串 , 这里的动态规划解法也是以 先遍历出 以某个节点为结束节点的所有子序列 的思路
对于刚接触动态规划的, 我感觉熟悉第三种遍历方式是需要抓住的核心
因为我们通常的惯性思维是以子序列的开头为基准，先遍历出以 a 为开头的所有子序列，再遍历出以 b 为开头的…但是动态规划为了找到不同子序列之间的递推关系，恰恰是以子序列的结束点为基准的，这点开阔了我们的思路。
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];
for (int x : nums) {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
}
return maxAns;
}
}
