蟻本 P.60 01ナップサック問題その2

評価対象を変える...?
理解理解
→いきなり漸化式でやろうとする
できない
→メモ化再帰してかんがえる
できた。

import java.util.Scanner;
public class Main {
  static int n;
  static int[] w;
  static int[] v;
  static int W;
  static int[][] dp;
  static int INF = 999999999;
  static int V;
  
  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();
    V = 0;
    for(int i = 0; i < n; i++) {
      V += v[i];
    }
    
    
    dp = new int[n+1][V+1];
    for(int i = 0; i <= n; i++) {
      for(int j = 1; j <= V; j++) {
        dp[i][j] = INF;
      }
    }
    int ans = INF;
    sorv();
    for(int i = V; i >= 0; i--) {
      if(dp[0][i] <= W) {
        ans = i;

        break;
      }
      System.out.println(dp[0][i]);
    }
    System.out.println(ans);
  }

  static void sorv() {
    for(int i = n-1; i >= 0; i--) {
      for(int j = 0; j <= V; j++) {
        if(j < v[i]) {
          dp[i][j] = dp[i+1][j];
        }
        else {
          int c1 = dp[i+1][j];
          int c2 = dp[i+1][j-v[i]]+ w[i];
          dp[i][j] = (c1 < c2)?c1:c2;
        }
        
      }
    }
  }


}