动态规划01 背包问题（算法）

/**
     * 背包5kg，物品为三个，
     * {1,2,4} 重量
     * {6,10,12}价值
     * dp 行代表物品，列代表容量。
     */
    public static void main(String[] args) {
        int[] value = {6, 10, 12};
        int[] weight = {1, 2, 4};
 
        int wu = 3;
        int kg = 5;
 
        int[][] dp = new int[wu + 1][kg + 1];
 
        for (int i = 1; i <= wu; i++) {
            for (int j = 1; j <= kg; j++) {
                if (weight[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
                } else {
                    // 放入上一列的
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
 
        for (int i = 1; i <= wu; i++) {
            System.out.print("第"+i+"个物品"+"      ");
            for (int j = 1; j <= kg; j++) {
                System.out.print(dp[i][j]+"      ");
            }
            System.out.println("");
        }
 
        System.out.println(dp[wu][kg]);
    }
 
 
 public static void main(String[] args) {
        int[][] wp = new int[3][2];
        wp[0][0] = 1;
        wp[0][1] = 6;
        wp[1][0] = 2;
        wp[1][1] = 10;
        wp[2][0] = 4;
        wp[2][1] = 12;
 
        int[] dp = new int[5 + 1];
   
        for (int i = 0; i < 3; i++) {
            // 当前 物体重量 小于等于 背包重量
            for (int j = dp.length - 1; j >= wp[i][0]; j--) {
                dp[j] = Math.max(dp[j], dp[j - wp[i][0]] + wp[i][1]);
            }
        }
        System.out.println(dp[dp.length - 1]);
    }