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

为了解决给定的背包问题，我们可以使用动态规划的方法，特别是“0-1”背包问题的优化解法。这种方法利用了滚动数组技术，以节省内存，同时提高时间效率。

方法思路

我们将使用一个一维数组dp来表示当前处理物品时的状态。dp[j]表示当前情况下，总体积不超过j时的最大价值。我们可以将物品按照顺序处理，并从容量M开始向下处理，这样可以确保每个状态只计算一次，避免重复计算。

具体步骤如下：

解决代码

int knapSack(int[] w, int[] v, int C) {
    int n = w.length;
    int[] dp = new int[C + 1];
    
    // 初始化第一个物品
    for (int j = 0; j <= C; j++) {
        if (w[0] <= j) {
            dp[j] = v[0];
        } else {
            dp[j] = 0;
        }
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = C; j >= w[i]; j--) {
            if (dp[j - w[i]] + v[i] > dp[j]) {
                dp[j] = dp[j - w[i]] + v[i];
            }
        }
    }
    
    return dp[C];
}

代码解释

这种方法确保了时间复杂度为O(N * C)，空间复杂度为O(C)，适用于题目给定的约束条件。