蟻本 P.58 個数制限なしナップサック問題

わけがわからない
→解説読む
わけがわからない
→解説読む
わけがわからない
→お風呂入る
わかる

import java.util.Scanner;
public class Main {
  static int n;
  static int[] w;
  static int[] v;
  static int W;
  static int[][] dp;
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    n = stdIn.nextInt();
    w = new int[n];
    v = new int[n];
    for(int i = 0; i < n; i++) {
      w[i] = stdIn.nextInt();
      v[i] = stdIn.nextInt();
    }
    W = stdIn.nextInt();
    
    dp = new int[n+1][W+1];
    int ans = sorv();
    System.out.println(ans);
  }
  
  static int sorv() {
    for(int i = n-1; i >= 0; i--) {
      for(int j = 0; j <= W; j++) {
        if(j - w[i] < 0) {
          dp[i][j] = dp[i+1][j];
        }
        else {
          int c1 = dp[i+1][j];
          int c2 = dp[i][j-w[i]] + v[i];
          dp[i][j] = (c1 < c2)?c2:c1;
        }
      }
    }
    
    return dp[0][W];
  }


}