一、动态规划

  动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。

二、基本思想

  （1）将大问题划分为小问题进行解决，从而一步步获得最优解；
  （2）动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
  （3）与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。（即下一次求解是在上一次得到的最优解基础上进行的）
  （4）可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。具体的动态规划算法多种多样，但它们具有相同的填表格式。

三、简单实例（背包问题）

  （1）背包问题：有一个容量为4磅的背包，现有以下物品

物品	重量（磅）	价格（$）
吉他（G）	1	1500
音响（S）	4	3000
电脑（L）	3	2000

  求在容量允许下能够装入放入最大价值是多少？（每个物品只能装入一次）
  （2） 解题思路：
  利用动态规划，每次遍历到的第i个物品，根据 w [ i − 1 ] w[i-1] w[i−1]和 v a l [ i − 1 ] val[i-1] val[i−1]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设 v a l [ i − 1 ] val[i-1] val[i−1]、 w [ i − 1 ] w[i-1] w[i−1]分别为第i个物品的价值和重量（这里 i − 1 i-1 i−1是因为数组下标的原因）,M为背包的容量。再令 v [ i ] [ j ] v[i][j] v[i][j]表示在前 i i i个物品中能够装入容量为 j j j的背包中的最大价值。则我们有下面的结果：

第一步：初始化v[i][0]=v[0][i]=0;//表示填入表第一行和第一列是0；
第二步：当w[i]>j时: v[i][j]=v[i-1][j]//当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略；
第三步：当j>=w[i]时:v[i][j]=max{v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]}//当准备加入的新增的商品的容量小于等于当前背包的容量，v[i-1][j]：就是上一个单元格的装入的最大值，val[i-1]：表示当前商品的价值，v[i-1][j-w[i-1]]：装入第i-1个物品，剩余的空间可装入的最优解。

  （3）动态规划图表：

	0磅	1磅	2磅	3磅	4磅
	0	0	0	0	0
吉他（G）	0	1500	1500	1500	1500
音响（S）	0	1500	1500	1500	3000
电脑（L）	0	1500	1500	2000	3500

  （4）代码实现：

package com.haiyang.algorithm.dp;

/**
 * @author haiYang
 * @create 2022-01-28 16:33
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = new int[]{1, 4, 3};//物品重量
        int[] val = new int[]{1500, 3000, 2000};//物品价格
        int m = 4;//背包容量
        int n = val.length;//物品个数

        int[][] v = new int[n + 1][m + 1];//记录前i个物品中能够装入容量为j的背包中的最大值
        int[][] path = new int[n + 1][m + 1];
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[i].length; j++) {
                if (w[i - 1] > j) {//w[i-1]：第i个物品的数组下标为i-1，当第i个物品的重量大于背包容量，表示装不下这个物品，因此最大值为v[i-1][j]
                    v[i][j] = v[i - 1][j];
                } else {
                    //val[i-1] + v[i-1][j-w[i-1]]:表示装入第i-1个物品的价值加上剩余空间能够装的最大价值
                    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[i][j] = 1;//标记该物品加入背包，便于查看那些物品加入背包
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }

        }
        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();

        }
        int i = path.length - 1;
        int j = path[0].length - 1;
        //回溯输出加入背包的物品
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                System.out.println("第" + i + "个物品加入背包！");
                j = j - w[i - 1];
            }
            i--;
        }
    }
}