动态规划解决01背包问题

import java.util.Arrays;

public class ZeroOneKnapsack {
    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};

        int bag_room = 4;
        int[][] dp = new int[weight.length][bag_room+1];

        for(int j = weight[0]; j < bag_room+1; j++){
            dp[0][j] = value[0];
        }
        for(int i = 1; i < weight.length; i++){
            for(int j = 0; j < bag_room+1; j++){
                if(weight[i] > j){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
                }
            }
        }

        for(int i = 0; i < dp.length; i++){
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println(dp[2][bag_room]);
    }
}

dp数组

        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};

[0, 15, 15, 15, 15]
[0, 15, 15, 20, 35]
[0, 15, 15, 20, 35]
35

dp数组

      int[] weight = {3, 4, 1};
      int[] value = {20, 30, 15};

[0, 0, 0, 20, 20]
[0, 0, 0, 20, 30]
[0, 15, 15, 20, 35]
35

dp数组

        int[] weight = {4, 3, 1};
        int[] value = {30, 20, 15};

[0, 0, 0, 0, 30]
[0, 0, 0, 20, 30]
[0, 15, 15, 20, 35]
35