import java.util.LinkedList;

public class Main{
    /*
      由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]
      由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，
      那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
     */
    static void test_2_wei_bag_problem1() {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;//包的容量

        bagWeight = 6;//包的容量
        weight=new int[]{1,2,3,4,5};
        value=new  int[]{2,4,4,5,6};

        bagWeight = 100;//包的容量
        weight=new int[]{77,22,29,50,99};
        value=new  int[]{92,22,87,46,90};


        // 二维数组
        int[][] dp = new int[weight.length][bagWeight + 1];
        // 初始化
        //初始化第一列 weight[0]
        for (int i = 1; i < dp[0].length; i++) {
            if (i >= weight[0]) {
                dp[0][i] = value[0];
            }
        }
        //容量为0
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        // weight数组的大小 就是物品个数
        for (int i = 1; i < weight.length; i++) { // 遍历物品
            for (int j = 1; j <= bagWeight; j++) { // 遍历背包容量
                if (j < weight[i]) 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]);

            }
        }
        System.out.println(dp[weight.length - 1][bagWeight]);
    }

    public static void test_2_wei_bag_problem0() {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 6;//包的容量

        bagWeight = 6;
        weight=new int[]{1,2,3,4,5};
        value=new  int[]{2,4,4,5,6};

        bagWeight = 100;//包的容量
        weight=new int[]{77,22,29,50,99};
        value=new  int[]{92,22,87,46,90};
        helper(weight,value,bagWeight,0);
        System.out.println(sum);
    }

    public static LinkedList<Integer> list = new LinkedList<>();
    public static int sum = 0;

    public static void helper(int[] weight, int[] value, int bagWeight, int index) {
        if (index >= weight.length)
            return;
        if (bagWeight >= 0) {
            int cnt = 0;
            for (Integer i :
                    list) {
                cnt+=i;
            }
            sum=Math.max(sum,cnt);
        }

        list.add(value[index]);
        helper(weight, value, bagWeight - weight[index], index + 1);
        list.pollLast();
        helper(weight, value, bagWeight, index + 1);

    }

    public static void main(String[] args) {
        test_2_wei_bag_problem1();
        test_2_wei_bag_problem0();
    }
}