动态规划

01背包与无限背包

public class KnapsackProblem {
    public static void main(String[] args) {
        //动态规划可以用填表法
        //每个物品的重量
        int[] w = {1, 4, 3};
        //每个物品的价值
        int[] v = {1500, 3000, 2000};
        int m = w.length;
        //背包的容量
        int bag = 4;
        //定义容量和价值的二维数组，行=物品数量+1，列=背包容量+1
        int[][] val = new int[m + 1][bag + 1];
        //    val[0][j]、val[i][0]默认都是1
        //    给数组赋值
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < bag + 1; j++) {
                if (j < w[i - 1]) {
                    val[i][j] = val[i - 1][j];
                } else {
                    //注意这里 val[i][j-w[i-1]], 这说明当 j>=w[i-1]，即背包容量大于当前这个物体重量的时候，
                    // 此时背包最大价值=（在背包容量=当前背包容量减去这个物体的重量 的时候，
                            //并且可以放入这个物体的时候所能承载的最大价值）
                    //这样说有点绕口，还没有代码好理解。
                    //总之，就是在容量为 j-w[i-1]的时候，val[i][]可以装入当前这个物体。   
                            //val[i-1][]不能装入当前物体
                    //一个是01背包，一个是无线背包
                    val[i][j] = Math.max(val[i - 1][j], v[i - 1] + val[i-1][j - w[i - 1]]);
                }
            }
        }
        for (int i = 0; i < val.length; i++) {
            for (int j = 0; j < val[0].length; j++) {
                System.out.print(val[i][j] + "\t");
            }
            System.out.println();
        }
    }
}