*[Python] 12865-평범한 배낭

1. 개념 정의
  - N: 물품의 수(1 ≤ N ≤ 100)
  - K: 버틸 수 있는 무게(1 ≤ K ≤ 100,000)
  - W: 물건의 무게(1 ≤ W ≤ 100,000)
  - V: 물건의 가치(0 ≤ V ≤ 1,000)

2. 문제 이해
  - 준서는 여행을 떠나며 N개의 물건을 챙긴다. 각 물건은 (무게 W, 가치 V)를 가진다.
    배낭에 넣은 물건의 V 만큼 준서는 즐길 수 있다. 다만 최대 K무게까지만 들고 다닐 수 있다.
    이제 준서가 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구해야 한다. 

3. 로직 짜기
  1. 가치 V를 내림차순으로 정렬 후 K를 넘지 않게 해서 가방에 넣으면?
    - 최대 가치의 무게가 지나치케 클 경우 최적화 불가능
  2. 무게당 가치(가치/무게)가 큰 순으로 내림차순 정렬 후 차례대로 넣으면?
    - 물건을 나눌 수 있는 경우라면 좋겠지만, 여기선 그렇지 않음
    - 또한 N가 커지면 문제 발생
  *3. 각 무게마다 최대 가치를 구해 보면? 
   - 이중배열(table)을 사용해 해결 가능하다
     - 현재(i) 무게(cur_weight)는 자신보다 작은 무게(low_weight)에 아무런 영향을 끼치지 못한다
        - 그러므로 W보다 작은 무게(low_weight)의 가치는, 그 이전 차례의 가치를 그대로 가진다
        - 즉, table[i][low_weight]의 가치 = table[i-1][low_weight]의 가치
     - 현재(i) 무게(cur_weight) 이상의 무게의 경우(big_weight )에는 크기 비교가 필요하다
        - [이전 차례의 big_weight 가치] vs [이전 차례의 (big_weight - cur_weight) + 현재 가치(V)의 가치]
        - 즉, table[i][big_weight ]의 가치 =
                       max( table[i-1][big_weight ] 가치, table[i-1][big_weight - cur_weight] + 현재 가치(V) )

N, K = map(int, input().split())
table = [[0] * (K+1) for _ in range(N+1)]

for i in range(1, N+1):
    W, V = map(int, input().split())
    for j in range(1, K+1):
        if j < W:
            table[i][j] = table[i-1][j]
        else:
            table[i][j] = max(table[i-1][j], table[i-1][j-W] + V)
print(table[N][K])

4. 출처: www.acmicpc.net/problem/12865