算法-动态规划

动态规划算法介绍
1.动态规划(Dynamic Programming)算法核心思想：大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。
2.适用于动态规划求解的问题，经分解得到子问题往往不是相互独立的，即下一阶段的求解建立在上一个子阶段的基础上。
3.动态规划可以使用填表的方式逐步推出，得到最优解。

01背包问题

思路分析：

遍历第i个物品，根据w[i]和v[i]确定是否需要将物品放入背包中。
给定n个物品，设v[i] w[i]分别为第i个物品的价值和重量。
新的物品可以装入，则判断原来的价值 和 新物品+剩余空间最大价值 的max
遍历背包的每一磅j
①当v[i][0]=v[0][j]=0 //表格第一行和第一列为0
②当w[i]>j : v[i][j] = v[i-1][j] //准备加入的商品重量大于j的重量 使用上一次的装入策略
③当j >= w[i]时 ：v[i][j] = max{v[i-1][j], v[i] + v[i-1][j-w[i]]} //准备加入的商品小于等于背包容量，
v[i-1][j]：上个背包最大值
v[i]:当前商品价值
v[i-1][j-w[i]]:装入i-1商品 到剩余空间j-w[i]的最大值

java实现：

public static void main(String[] args) {
        int[] w = {1,4,3}; //物品重量
        int[] val = {1500,3000,2000}; //物品价格 这里val[i] 就是 前面的v[i]
        int m = 4; //背包容量
        int n = val.length; //物品个数

        //记录放入商品情况
        int[][] path = new int[n+1][m+1];

        //创建二维数组
        //v[i][j] 表示前i个物品中能够装入容量为j的背包中的最大价值
        int[][] v = new int[n+1][m+1];

        //初始化第一行和第一列 默认也为0
        for(int i=0; i< v.length;i++){
            v[i][0] = 0;
        }
        for(int i=0; i < v[0].length; i++){
            v[0][i] = 0;
        }

        //动态规划处理
        for(int i=1; i<v.length;i++){
            for(int j =0; j <v[i].length; j++){
                //公式
                if(w[i-1] > j){ //程序从1开始 公式中的i - 1
                    v[i][j] = v[i-1][j];
                }else {
                    //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[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.printf("第%d个商品放入背包\n",i);
                j -= w[i-1];
            }
            i--;
        }

    }