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

为了解决这个问题，我们需要找到一种方法来选择物品，使得总价值最大化，同时总重量不超过背包容量。这个问题属于完全背包问题，因为物品可以无限重复使用。

方法思路

我们可以使用动态规划来解决这个问题。动态规划的核心思想是通过构建一个二维数组 dp，其中 dp[i][j] 表示前 i 个物品，总重量为 j 时的最大价值。通过逐个考虑每个物品，并尝试不同的重量组合，我们可以填充这个二维数组，最终得到结果。

具体步骤如下：

解决代码

import java.util.Scanner;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];        // 初始化第一个物品        int firstW = w[0];        int firstV = v[0];        for (int j = 0; j <= W; j++) {            int k = j / firstW;            dp[0][j] = k * firstV;        }        // 初始化其他物品为0        for (int i = 0; i < n; i++) {            dp[i][0] = 0;        }        // 遍历每个物品        for (int i = 1; i < n; i++) {            for (int j = 1; j <= W; j++) {                int maxVal = 0;                int k = 1;                while (true) {                    int currentW = k * w[i];                    if (currentW > j) {                        break;                    }                    int currentV = k * v[i] + dp[i-1][j - currentW];                    if (currentV > maxVal) {                        maxVal = currentV;                    }                    k++;                }                dp[i][j] = maxVal;            }        }        return dp[n-1][W];    }}

代码解释

通过这种方法，我们可以高效地解决完全背包问题，确保在时间复杂度合理的范围内得到最优解。