基本介绍

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

实践：背包问题

问题描述

有一个背包，容量为 4 磅，现有如下物品：

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

要求装入背包的总价值最大，且重量不超出背包容量
装入物品不能重复（01背包）

思路分析

如基本介绍所说，我们不妨先列表寻找规律

物品	1磅	2磅	3磅	4磅
	0	0	0	0
吉他（G）	1500（G）	1500（G）	1500（G）	1500（G）
音箱（S）	1500（G）	1500（G）	1500（G）	3000（S）
电脑（L）	1500（G）	1500（G）	2000（L）	2000（L）+ 1500（G）

设 weight[i]、value[i] 分别表示第 i 个物品的重量和价值，total[i][j]表示前 i 个物品中能够装入容量为 j 的背包中的物品的的最大价值
每遍历一个物品，我们可以根据 weight[i]、value[i] 计算是否需要把他放入背包中（能够放入的前提下放入会使背包中物品的总价值增加就放入）
由图表易知：
- 当 weight[i] > j（当装入物品质量大于背包容量时，直接使用上一单元格的策略）
  
  total[i][j] = total[i - 1][j]
- 当weight[i] <= j（当装入物品质量小于背包容量时，表示可以装进去）
  
  total[i][j] = Max{ total[i - 1][j] , value[i] + total[i - 1][j - weight[i]]}
  
  total[i - 1][j]：上一单元格装入的最大值
  
  value[i] + total[i - 1][j - weight[i]]：装入前 i -1 商品到剩余空间 j - weight[i]的最大值

代码实现

其实整个代码实现过程就是依据上面分析的思路来还原整个图表！

package com.atguigu.dynamic;

public class KnapSackProblem   {

    public static void main(String[] args) {
        int[] value = {1500, 3000, 2000};       //各物品的价格
        int[] weight = {1, 4, 3};               //各物品的重量
        int catacity = 4;                       //背包的容量
        int num = value.length;                 //物品的个数

        //total[i][j] 表示再前 i 个物品中能够装入容量为j的背包中的最大价值
        int[][] total = new int[num + 1][catacity + 1];
        //记录放入商品的情况
        int[][] path = new int[num + 1][catacity + 1];


        for (int i = 1; i < total.length; i++) {    //i从1开始，不处理第一行
            for (int j = 1; j < total[0].length; j++) {     //j从1开始，不处理第一列
                //i 从 1 开始，所以第i个物品的重量应该表示为 weight[i - 1]
                if (weight[i - 1] > j) {
                    total[i][j] = total[i - 1][j];
                } else {
                    if (total[i - 1][j] < value[i - 1] + total[i - 1][j - weight[i - 1]]) {
                        total[i][j] = value[i - 1] + total[i - 1][j - weight[i - 1]];
                        //物品放入到背包中的同时需要用path记录
                        path[i][j] = 1;
                    } else {
                        total[i][j] = total[i - 1][j];
                    }
                }
            }
        }

        //遍历输出二维数组，即前面分析后得到的表格
        for (int i = 0; i < total.length; i++) {
            for (int j = 0; j < total[i].length; j++) {
                System.out.print(total[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 -= weight[i - 1];
            }
            i--;
        }
    }
}

输出结果：

【数据结构与算法】常用十大算法：动态规划

基本介绍

分类

实践：背包问题

问题描述

思路分析

代码实现