问题描述：有 N 件物品和一个容量为 V 的背包。每件物品有且只有一件，第 i 件物品的体积为 v[i]，价值为 w[i]。求解将哪些物品放入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

状态定义：dp[i][j]表示考虑前 i 件物品中，且背包容量为 j 的前提下，所获得的最大价值。

状态转移：若已经完成了对前 i-1 件物品背包问题的求解（即小规模问题已解决），现在对于第 i 件物品，我们有两种情况考虑：

  • case1：选第 i 件物品，那么我们需要消耗当前的背包容量来换取物品的价值，即a=dp[i-1][j-v[i]]+w[i]，且j>=v[i]。
  • case2：不选第 i 件物品，那么我们则没有消耗当前的背包容量，只需要将前 i-1 件物品的状态转移过来即可，即b=dp[i-1][j]。

综上所述，状态转移方程为：dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])

注：在这里没有对状态方程的定义（下标从0开始 or 下标从1开始）和状态方程的初始化问题（初始化为 0 or INF）进行讨论，这个需要借助具体的问题背景具体分析。

原始解法

  • 时间复杂度：O(N * C)
  • 空间复杂度：O(N * C)
    1. class Solution {
    2.   public int maxValue(int N, int C, int[] v, int[] w) {
    3.       int[][] dp = new int[N][C+1];
    4.       // 先处理「考虑第一件物品」的情况
    5.       for (int i = 0; i <= C; i++) {
    6.           dp[0][i] = i >= v[0] ? w[0] : 0;
    7.       }
    8.       // 再处理「考虑其余物品」的情况
    9.       for (int i = 1; i < N; i++) {
    10.           for (int j = 0; j < C + 1; j++) {
    11.               // 不选该物品
    12.               int n = dp[i-1][j]; 
    13.               // 选择该物品，前提「剩余容量」大于等于「物品体积」
    14.               int y = j >= v[i] ? dp[i-1][j-v[i]] + w[i] : 0; 
    15.               dp[i][j] = Math.max(n, y);
    16.           }
    17.       }
    18.       return dp[N-1][C];
    19.   }
    20. }

滚动数组

  • 时间复杂度：O(N * C)
  • 空间复杂度：O(C)
    1. class Solution {
    2.   public int maxValue(int N, int C, int[] v, int[] w) {
    3.       int[][] dp = new int[2][C+1];
    4.       // 先处理「考虑第一件物品」的情况
    5.       for (int i = 0; i < C + 1; i++) {
    6.           dp[0][i] = i >= v[0] ? w[0] : 0;
    7.       }
    8.       // 再处理「考虑其余物品」的情况
    9.       for (int i = 1; i < N; i++) {
    10.           for (int j = 0; j < C + 1; j++) {
    11.               // 不选该物品
    12.               int n = dp[(i-1)&1][j]; 
    13.               // 选择该物品
    14.               int y = j >= v[i] ? dp[(i-1)&1][j-v[i]] + w[i] : 0;
    15.               dp[i&1][j] = Math.max(n, y);
    16.           }
    17.       }
    18.       return dp[(N-1)&1][C];
    19.   }
    20. }

一维优化

image.png

  • 时间复杂度：O(N * C)
  • 空间复杂度：O(C) ```java

class Solution { public int maxValue(int N, int C, int[] v, int[] w) { int[] dp = new int[C + 1]; for (int i = 0; i < N; i++) { for (int j = C; j >= v[i]; j—) { // 不选该物品 int n = dp[j]; // 选择该物品 int y = dp[j-v[i]] + w[i]; dp[j] = Math.max(n, y); } } return dp[C]; } } ```