动态规划

动态规划

还是回到贪心算法中的背包问题，使用贪心算法解决背包问题，得到的并不是最优解，而是一个近似算法。那么如何得到最优解呢，那就是动态规划。

动态规划是先解决子问题，在逐步解决大问题

• 动态规划可在给定约束条件下找到最优解
• 在问题可分解为彼此独立且离散的子问题时，可使用动态规划来解决

在动态规划中，每种动态规划解决方案都涉及到网格，每个单元格的值就是要优化的值，每个单元格都是一个子问题

这里的计算公式为

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

        int[] w = {3, 1, 4};//物品的重量
        int[] val = {2000, 1500, 3000};//物品的价值

        String[] names = {"笔记本电脑","吉他", "音响"};


        int m = 4;//背包的容量
        int n = val.length;//物品的个数

        //为了记录放入商品的情况，我们定义一个二维数组
        String[][] path = new String[n + 1][m + 1];
        for (String[] strings : path) {
            Arrays.fill(strings, "");
        }

        //创建二维数组
        //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 - 1] > j) {
                    v[i][j] = v[i - 1][j];
                    path[i][j] = path[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]];
                        
                        String goods = names[i-1]+"+"+path[i - 1][j - w[i - 1]];

                        path[i][j] = goods.lastIndexOf("+") == goods.length() -1 ? goods.substring(0,goods.length() -1)
                                : goods;
                    } else {
                        v[i][j] = v[i - 1][j];
                        path[i][j] = path[i-1][j];
                    }
                }
            }
        }

        //输出二维数组：
        for (int[] ints : v) {
            System.out.println(Arrays.toString(ints));
        }

        for(int i = 1;i<path.length;i++){
            for(int j = 1;j<path[i].length;j++){
                System.out.print(path[i][j]+"\t\t\t");
            }
            System.out.println();
        }

    }

}