評価対象を変える...?
理解理解
→いきなり漸化式でやろうとする
できない
→メモ化再帰してかんがえる
できた。
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; } } } } }