[백준]12865번 평범한 배낭

물건을 배낭에 담을 때
1. 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크면 넣지 않음
2. 다음 중 더 나은 가치를 선택해 넣음
2-1) 현재 넣을 물건의 무게만큼 배낭에서 빼고 현재 물건을 넣음
2-2) 현재 물건을 넣지 않고 이전 배낭 그대로 가지고 감

현재 담을 물건의 인덱스: i, 현재 가방 허용 용량: j 현재 담을 물건의 무게: w, 가치: v
1. j < w -> d[i][j] = d[i-1][j]
2. d[i][j] = max(d[i-1][j-w]+v, d[i-1][j])

public class Main {
   static int n, k;
   public static void main(String[] args) throws IOException {
       BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());
       n = Integer.parseInt(st.nextToken());
       k = Integer.parseInt(st.nextToken());

       int [][] info = new int[n+1][2];
       for (int i = 1; i <= n; i++) {
           String input = br.readLine();
           String[] str = input.split(" ");
           info[i][0] = Integer.parseInt(str[0]);
           info[i][1] = Integer.parseInt(str[1]);
       }


       int [][]dp = new int[n+1][k+1];

       for (int i = 1; i <= n; i++) {
           for (int j = 1; j <= k; j++) {
               if (info[i][0] > j) {
                   dp[i][j] = dp[i-1][j];
               }
               else {
                   dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-info[i][0]] + +info[i][1]);
               }
           }
       }
       System.out.println(dp[n][k]);
   }
}

dp 문제는 점화식을 찾는 것이 관건임