[백준] 12865 평범한 배낭 #python

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

12865번: 평범한 배낭

 

Input

4 7

6 13

4 8  

3 6

5 12

DP	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1(6, 13)	0	0	0	0	0	0	13	13
2(4, 8)	0	0	0	0	8	8	13	13
3(3, 6)	0	0	0	6	8	8	13	14
4(5, 12)	0	0	0	6	8	12	13	14

현재물건(row), 현재 배낭에 최대로 넣을 수 있는 무게(column) 

dp[i][j] = 배낭에 최대로 넣을 수 있는 무게에서, max(현재 물건을 넣었을때의 가치 , 현재 물건을 넣지않았을때의 가치)

단, 이 때 배낭의 최대무게가 현재물건의무게보다 작으면, 현재물건을 넣을 수 없으므로 이 전의 물건들의 최대 가치를 저장해준다.

 

n, weight = map(int, input().split())
arr = [(0, 0)]

for _ in range(n):
    a, b = map(int, input().split())
    arr.append((a, b))

dp = [[0]*(weight+1) for _ in range(n+1)] # dp생성

for i in range(1, n+1):
    tmp_w, tmp_v = arr[i][0], arr[i][1]
    for j in range(1, weight+1):
        if j < tmp_w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-tmp_w]+tmp_v, dp[i-1][j])

print(dp[-1][-1])