### 0-1 Knapsack: Backtracking with Memoization (Java)

Source: https://github.com/gaoshengnan/leetcode/blob/master/src/main/java/theoreticalBasis/背包/backpack.md

This solution to the 0-1 Knapsack problem uses a recursive backtracking approach combined with memoization to avoid redundant calculations. For each item, there are two choices: include it in the backpack or not. The function `f(i, curLoadSum, n, bpWeight)` explores these choices, pruning branches where the current load exceeds the backpack's capacity. Memoization is applied using a `mem` array to store results for `(i, curLoadSum)` states, significantly improving performance by preventing re-computation of already visited states.

```Java
/**
     *
     * 解法1 回溯 + 记忆化递归
     *
     * @param i: 考察到哪个物品
     * @param curLoadSum: 当前已经装进去的物品的重量和
     * @param n：物品个数
     * @param bw：背包可承受重量
     */
    private void f(int i, int curLoadSum, int n, int bpWeight) {
        if (curLoadSum == bw || i == n) {//装满了或者物品全部考察完
            //if (curLoadSum > maxW) maxW = curLoadSum;
            maxW = Math.max(maxW, curLoadSum);
            return;
        }
        if (mem[i][curLoadSum]) return;
        mem[i][curLoadSum] = true;//记忆化递归存储
        f(i + 1, curLoadSum, n, bpWeight);//不装第 i 件物品
        if (curLoadSum + weights[i] <= bw)//若加上 i 件物品，小于背包承载重量，再继续装 (剪枝)
            f(i + 1, curLoadSum + weights[i], n, bpWeight);//装第 i 件物品
    }
```

--------------------------------

### 0-1 Knapsack: Dynamic Programming Solution (Java)

Source: https://github.com/gaoshengnan/leetcode/blob/master/src/main/java/theoreticalBasis/背包/backpack.md

This dynamic programming solution for the 0-1 Knapsack problem divides the process into 'n' stages, one for each item. A 2D boolean array `s[n][bw + 1]` tracks reachable states (total weights) at each stage. For each item, it considers two possibilities: not including the item (inheriting states from the previous stage) or including the item (shifting previous states by the item's weight). The final maximum weight is found by iterating backward through the last row of the `s` array to find the largest reachable weight.

```Java
/**
     *
     * 解法2 动态规划
     *
     * @param n：物品个数
     * @param bw: 当前已经装进去的物品的重量和
     * @return 最大可以装多少重量
     */
    private int dpBackpack (int n, int bw) {
        boolean[][] s = new boolean[n][bw + 1];//初始化二维数组
        s[0][0] = true;//第一件物品不装
        if (weights[0] <= bw) s[0][weights[0]] = true;//第一件物品装
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= bw ; j++) {//选择不装 i 件物品
                if (s[i - 1][j]) s[i][j] = s[i - 1][j];
            }
            for (int j = 0; j <= bw - weights[i]; j++) {//选择装 i 件物品
                if (s[i - 1][j]) s[i][j + weights[i]] = true;
            }
        }

        for (int i = bw; i >= 0; i--) {//最后一层找到最大值
            if (s[n - 1][i]) return i;
        }
        return 0;
    }
```

=== COMPLETE CONTENT === This response contains all available snippets from this library. No additional content exists. Do not make further requests.