# Knapsack

0-1 背包问题
问题：给大小为n的数组weights[]和values[], 求在不超过W的情况下能取得的value总和最大是多少，每一个数只能最多取一次（或者不取）

本质是排列组合，复杂度O(2^n)

public static void main(String[] ss) {

        int[] a = {1,2,3};
        int[] b = {4,2,1};
        int w = 3;

        System.out.println(knap(a, b, w));

    }

    private static int maxValue = 0;
    private static int knap(int weights[], int values[], int maxW) {
        dfs(weights, values, 0, 0, 0, maxW);
        return maxValue;
    }


    private static void dfs(int[] weights, int[] values, int curV, int curW, int index, int maxWeight) {
        if (curW > maxWeight) {
            return;
        }

        maxValue = Math.max(maxValue, curV);
        for (int i = index; i < weights.length; i++) {
            dfs(weights, values, curV + values[i], curW + weights[i], i + 1, maxWeight);
        }
    }

另一种写法。这种写法更容易看出我们可以用[index, curW] = weight来标记每一个状态（递归树上的结点）
O(2^n)

    private static int knap(int weights[], int values[], int maxW) {
        return dfs(weights, values, 0, 0, maxW);
    }

    private static int dfs(int[] weights, int[] values, int curW, int index, int maxWeight) {
        if (index == weights.length) {
            return 0;
        }
        int max_1 = 0;
        if (curW + weights[index] <= maxWeight) {
            max_1 = dfs(weights, values, curW + weights[index], index + 1, maxWeight) + values[index];
        }
        int max_2 =  dfs(weights, values, curW, index + 1, maxWeight);
        return Math.max(max_1, max_2);
    }

Memoization
O(maxW * n)

private static int knap(int weights[], int values[], int maxW) {
        int n = weights.length;
        int[][] dp = new int[n][maxW + 1];

        return dfs(weights, values, 0, 0, maxW, dp);
    }

    private static int dfs(int[] weights, int[] values, int curW, int index, int maxWeight, int[][] dp) {
        if (index == weights.length) {
            return 0;
        }

        if (dp[index][curW] != 0) {
            return dp[index][curW];
        }
        int max_1 = 0;
        if (curW + weights[index] <= maxWeight) {
            max_1 = dfs(weights, values, curW + weights[index], index + 1, maxWeight, dp) + values[index];
        }
        int max_2 =  dfs(weights, values, curW, index + 1, maxWeight, dp);
        int rt = Math.max(max_1, max_2);
        dp[index][curW] = rt;

        return rt;
    }

iterative dp, 通项公式跟递归是一摸一样
O(maxW * n)

private static int knap(int weights[], int values[], int maxW) {
        int n = weights.length;
        int[][] dp = new int[n][maxW + 1];

        for (int i = 0; i < maxW + 1; i++) {
            if (weights[0] <= i) {
                dp[0][i] = values[0];
            }
        }

        for (int i = 1; i < n; i ++) {
            for (int j = 1; j < maxW + 1; j++) {
                if (j - weights[i] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n - 1][maxW];
    }

可以发现当前的dp[row]只依赖于之前一行dp[row - 1], 所以可以简化为一维dp

    private static int knap(int weights[], int values[], int maxW) {
        int n = weights.length;
        int[] dp1 = new int[maxW + 1];
        int[] dp2 = new int[maxW + 1];

        for (int i = 0; i < maxW + 1; i++) {
            if (weights[0] <= i) {
                dp1[i] = values[0];
            }
        }
        
        for (int i = 1; i < n; i ++) {
            for (int j = 1; j < maxW + 1; j++) {
                if (j - weights[i] >= 0) {
                    dp2[j] = Math.max(dp1[j], dp1[j - weights[i]] + values[i]);
                }else {
                    dp2[j] = dp1[j];
                }
            }

            int[] tmp = dp1;
            dp1 = dp2;
            dp2 = tmp;
            Arrays.fill(dp2, 0);
        }

        return dp1[maxW];
    }

Unbounded knapsack
如果按0-1的解法的话会形成3个嵌套的for循环
换一种思路
 , ${\displaystyle w_{i}\leq w}$, 
O(n * maxW)

private static int knap(int weights[], int values[], int maxW) {
        int n = weights.length;
        int[] dp = new int[maxW + 1];

        for (int i = 1; i < maxW + 1; i++) {
            for (int j = 0; j < n; j++) {
                if (i >= weights[j]) {
                    dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);
                }
            }
        }

        return dp[maxW];
    }
       

ToDo
可以用贪心算法吗？v / w 最大的那个一直加

Bounded knapsack