动态规划

动态规划的原理其实也是将大问题划分为小问题，从而一步步获取最优解，但是适用于动态规划求解的问题，子问题往往不是独立的，是具有相互关联性。

背包问题

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

①要求达到的目标为装入的背包的总价值最大，并且重量不超出

②装入的物品不能重复

思路分析

对于这个题首先最合适的就是列表来分析，找出规律：

由于是按照吉他-音响-电脑的顺序放入的背包，可以得到明显的两种情况：

①当放的东西小于背包容量时，最优价格即为上一个单元格的装入策略。

②当放的东西大于背包容量时，最优价格即为上一个单元格的装入策略与装入本物品后的最优策略进行比较。

由此产生核心的比较代码：

 for (int i = 1; i < v.length ; i++) {
            for (int j = 1; j < v[0].length ; j++) {//两次遍历
                if(w[i - 1] > j){//第一种情况
                    v[i][j] = v[i - 1][j];
                }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];
                    }
                }

            }
        }

当思路梳理清楚以后，核心代码就很简单了(体现了动态规划的顺序性与关联性)

全部代码:

public class KnapProblem {
    public static void main(String[] args) {
        int w[] = {1,4,3};
        int[] val = {1500,3000,2000};
        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];
        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 = 1; j < v[0].length ; j++) {
                if(w[i - 1] > j){
                    v[i][j] = v[i - 1][j];
                }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();
        }
       //思考如何输出最终结果
       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 --;
       }
    }
}