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

问题描述

我们需要解决一个典型的0-1背包问题：给定n个物品，每个物品都有一个重量wi和一个价值vi。我们的目标是从这些物品中选择一些，使得总重量不超过给定的容量W，同时使得所选物品的总价值最大化。

解决思路

传统的动态规划方法处理这个问题时，通常会采用以下策略：对于每个物品，我们可以选择拿取0、1、2、3...k个，然后剩余的容量中我们需要查询上一行对应的列，以找到最大的价值。然而，我们发现一个关键的优化点：对于当前物品，我们可以直接选择是否拿取它，而不是枚举所有可能的拿取次数。具体来说，我们可以这样处理：

这种方法的核心在于，当我们拿取一个物品后，剩余的重量可以继续使用同一行的动态规划结果，这样可以避免重复计算多次循环，显著降低时间复杂度。

具体代码

import java.util.Scanner;import static java.lang.Math.max;public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int w[] = new int[n];        int 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();        }        int W = sc.nextInt();        int res = solution(w, v, n, W);        System.out.println(res);        sc.close();    }    private static int solution(int[] w, int[] v, int n, int W) {        int[][] dp = new int[n][W + 1];        // 初始化第一行与第一列        for (int i = 0; i <= W; i++) {            dp[0][i] = i / w[0] * v[0];        }        for (int i = 1; i < n; i++) {            for (int j = 1; j <= W; j++) {                if (j >= w[i]) {                    dp[i][j] = max(dp[i-1][j], v[i] + dp[i][j - w[i]]);                } else {                    dp[i][j] = dp[i-1][j];                }            }        }        return dp[n-1][W];    }}

代码解释

这种方法通过合理简化循环结构，避免了传统动态规划中的重复计算，显著提升了算法的效率。

转载地址：http://btwg.baihongyu.com/