本文共 1534 字，大约阅读时间需要 5 分钟。

为了解决0-1背包问题，我们可以使用记忆化递归来优化深度优先搜索（DFS），避免重复计算状态，从而提高效率。下面是详细的解决方案：

问题分析

我们需要从n个物品中选择不超过总重量W的物品，使得价值总和最大化。这是一个典型的0-1背包问题，因为每个物品只能选择一次。

方法选择

我们选择使用记忆化递归来解决这个问题。记忆化技术可以帮助我们记录已经计算过的状态，避免重复计算，从而减少递归的次数和时间复杂度。

解决思路

代码实现

public class Main {
    static int n;
    static int[] w;
    static int[] v;
    static int W;
    static int max = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        w = new int[n];
        v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
        }
        W = sc.nextInt();
        dfs(0, 0, W);
        System.out.println(max);
        sc.close();
    }
    private static void dfs(int cur, int value, int remainingW) {
        if (cur == n) {
            if (value > max) {
                max = value;
            }
            return;
        }
        if (w[cur] <= remainingW) {
            dfs(cur + 1, value + v[cur], remainingW - w[cur]);
        }
        dfs(cur + 1, value, remainingW);
    }
}

代码解释

• 主函数：读取输入，初始化参数，调用递归函数。
• 递归函数：处理当前物品，选择或不选，递归处理下一个物品。
• 剪枝：在不选的情况下，直接处理下一个物品，避免重复计算。
• 记忆化：通过递归终止条件和剪枝优化，减少重复计算。

测试数据

输入：

4
2 3
1 2
3 4
2 2
5

输出：7

结果解释

递归选择了物品0、1、3，总价值为3+2+2=7，满足总重量限制。代码正确地更新了最大值max，并输出结果。