[백준] 12865번 : 평범한 배낭

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

12865번: 평범한 배낭

 
테스트 케이스 

예제 입력 1 

4 7
6 13
4 8
3 6
5 12

예제 출력 1 

14

 
물품의 개수 4, 배낭에 넣을 수 있는 가치의 합7
 
아이템 1) 무게:6, 가치:13
아이템 2) 무게:4, 가치:8
아이템 3) 무게:3, 가치:6
아이템 4) 무게:5, 가치:12
 
결과 -> 아이템2, 아이템3으로 가치가 14 결과가 출력된다. 아이템1이 가장 가치가 높다고해서 아이템이 먼저 가방에 들어가게된다면 이후에 가치가 더 높은 아이템들이 들어 갈 수 없다. 따라서 아이템이 있는경우와 없는경우를 모두 생각하여 가치의 최대값을 구해야한다.
 
1. 아이템1 이 있는경우에서 아이템 2가 있는경우, 아이템2 가 없는경우
2. 아이템1 이 없는경우에서 아이템 2가 있는경우, 아이템2 가 없는경우
3. 아이템2가 있는경우에서 아이템3이 있는경우, 아이템3이 없는경우
4. 아이템2가 없는경우에서 아이템3이 있는경우, 아이템3이 없는경우
...
생략
와 같은 방식으로 결과를 도출 할 수 있다.

dp 테이블을 위와 같이 정리 할 수 있다. 아이템 3에서 7번째 무게를 계산할때 13 -> 14로 업데이트 된다.
그 이유는 아이템1 있는경우와 아이템1이 없는경우에서의 최대값을 선택하여 14가 선택된것이다.
즉, 13은 아이템이 3이 없는경우 14는 아이템3이 있는 경우이다. 아이템3이 있는경우는 8+6으로 나타 낼 수 있다 dp[아이템2][3]에서 자기자신의 아이템 가치를 더하면 된다. dp[아이템2][3]은 이미 최대값을 가진 Optimal Solution이기 때문이다.
 
따라서 다음과 같은 점화식을 만들 수 있다.
아이템 Index = i라고 하고 가방의 무게를 n이라고 하고 dp 테이블을 가치 최대값 이라고 가정한다면
dp[i][n] = max(dp[i][n-itemweight[i]] + itemvalue[i], dp[i-1][n]) # 아이템 i가 있는경우와 없는경우
 
w는 아이템의 무게 리스트, v는 아이템의 가치 리스트

N, W = map(int, input().split())

w = []
v = []
for _ in range(N):
    a ,b  = map(int, input().split())
    w.append(a) # 무게 배열
    v.append(b) # 가치 배열

dy = [[0 for _ in range(W+1)] for _ in range(len(v)+1)]

for i in range(1, len(v)+1): # 아이템
    for j in range(1, W+1): # 무게
        if(w[i-1] > j):
            dy[i][j] = dy[i-1][j]
        else :
            dy[i][j] = max(dy[i-1][j-w[i-1]] + v[i-1], dy[i-1][j]) # 추가하지 않은경우, 자기자신을빼고 물품을 추가한경우 중에서 Max 값을 선택한다.
            
print(dy[len(v)][W])