题解 | JAVA #01背包# [P0-T2]

推荐从头到尾看一遍背包问题九讲

时间: O(n*v)
空间: O(v)

import java.util.*;

public class Solution {
  // dp[i][j]: max weight of picking from first i items, using volume <= j 
  //  = Max {
  //    dp[i-1][j]           // not use i
  //    dp[i-1][j-vi] + wi   // use i
  public int knapsack (int V, int n, int[][] vw) {
    int[] dp = new int[V+1];
    for (int i = 0; i < n; i++) {
      int vi = vw[i][0], wi = vw[i][1];
      
      // reverse traverse to prevent dirty read
      // don't need to check j < vi since we know i won't fit.
      //   i.e. dp[i][j] = dp[i-1][j] in those cases.
      for (int j = V; j >= vi; j--) {
        dp[j] = Math.max(dp[j], dp[j-vi]+wi);
      }
    }
    return dp[V];
  }
}