BOJ 12865 평범한 배낭

https://www.acmicpc.net/problem/12865

dp와 그리디 알고리즘을 사용했다.

wvList[i] : i번째 물건의 무게(0th)와 가치(1th) 리스트
dp[i][j] : i번째 물건까지 사용 & 무게j일때 가치 (항상 최대가치를 넣도록!)

1. 물건 순서대로 for문 돌린다
2. i번째 물건 무게가 j보다 크다면(즉, 담을 수 없다면)
   => i-1번째 물건까지만 사용가능 => 이전값 그대로 덮어쓰기
3. i번째 물건 무게가 j보다 작다면(즉, 담을 수 있다면)
   => i번째 물건을 사용해보자! => (j-i물건무게)무게에서 가치 + i물건가치 로 계산할 수 있다.
   => i-1번째 물건까지만 사용한 가치 VS (j-i물건무게)무게에서 가치 + i물건가치
4. 위의 과정을 거치고 나면 dp에 j무게에서의 최대가치가 들어간다!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] wvList = new int[N+1][2];
        int[][] dp = new int[N+1][K+1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            wvList[i][0] = Integer.parseInt(st.nextToken());
            wvList[i][1] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= N; i++) { //i번째 물건 선택
            for (int j = 1; j <= K; j++) {
                if(wvList[i][0] > j) {
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j-wvList[i][0]]+wvList[i][1], dp[i-1][j]);
                }
            }
        }

        System.out.println(dp[N][K]);

    }

}