【动态规划算法 01背包问题 图解+画表】简单理解

图解+表 希望这篇博客可以帮助你理解动态规划

1、动态规划算法的思想

将大问题划分为小问题进行解决，从而一步步获取最优的处理办法 动态算法和分治算法类似，基本都是将求解的问题，我们先分为子问题，先求解子问题的解，然后从这些子问题的解得到原问题的解 与分治算法不同的是，适用于动态规的问题，经分解得到的子问题往往不是互相独立的，及就是下一个子问题的解是建立在上一个子阶段的基础上，进一步进行求解 动态规划可以通过填表的方式来逐步的推进

说了这么多，不如举个栗子实在，上题

2、01背包问题

01背包问题是动态规划算法的一个出名的题，所以一般这个题会了，别的类似于动态规划的问题，都是照猫画虎，因为题型有限题无限

背包问题：有一个背包容量四磅，现有如下物品：

要求：所装物品不能重复，不能超过背包容量，并且总价值最大

思路：每次遍历到第i个物品，根据w[i]和v[i]来确定是否要放入该物品，及就是给定的n个物品，设v[i],w[i]分别为第i个物品的价值和重量，C为被背包容量，再令v[i][j]来表示第前i个物品能够容量为j的背包的商品的最大价值

上面这段话比较难理解就是v[i][j]来表示第前i个物品能够容量为j的背包的商品的最大价值，ok，你不用理解了，下面通过画表的方式让你完全按理解：w[i]、v[i]、v[i][j] 为了更方便理解，我画了一个草图： 理解完上面的后，对于动态规划这类似，有专门的公式供我们使用： （1）v[i][0] =v[0][j] = 0 填入表的第一行第一列是0 （2）当w[i]>j时:v[i][j] = v[i-1][j] 当准备加入的商品的容量大于当前背包容量时，那就是无法添加，还是用上一个单元格的装入 （3）当j>=w[j]时：v[i][j] = max{v[i-1][j],v[i]+v[i-1][j-w[i]]} 这个说的就是我上图中加入重量为3的物品到当前背包容量为4时候的分析情景

代码如下：

public class Main16 {
          
   
    public static void main(String[] args) {
          
   

        int []w = {
          
   0,1,4,3};
        int[]v = {
          
   0,1500,300,2000};

        int m = 4;//背包容量
        int n = v.length-1;//物品个数

        //创建二维数据  v[i][j]表示在前i个物品中能够装入容量为j的背包的最大价值
        int[][] V = new int[n+1][m+1];
        for (int i = 1;i<V.length;i++){
          
   
            for (int j = 1;j<V[0].length;j++){
          
   
                if (w[i]>j){
          
   
                    V[i][j] = V[i-1][j];
                }else {
          
   
                    V[i][j] = Math.max(V[i-1][j],v[i]+V[i-1][j-w[i]]);
                }
            }
        }
        System.out.println(V[n][m]);
    }
}