[백준] 12865번(python 파이썬)

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

knapsack알고리즘 문제이다.

 

1. 배낭에 물건을 넣는다.

    - 물건을 넣기전 상태에서 (가방 무게 - 해당 물건 무게)의 가치 + 해당 물건 가치

2. 배낭에 물건을 넣지 않는다. 

    - 이전 값을 그대로 사용한다.

 

ex)

물건 개수 : 4

가방에 들어갈 수있는 최대 무게 : 7

1번 물건 : 6 13

2번 물건 : 4 8

3번 물건 : 3 6

4번 물건 : 5 12

dp[i][j]

1. 물건을 넣는다 : dp[i-1][j - 해당 물건 무게] + 해당 물건 가치

2. 물건을 넣지 않는다 : dp[i-1][j]

1, 2중 최대값을 넣는다.

가방무게 물건	0	1	2	3	4	5	6	7
1번 물건	0	0	0	0	0	0	13	13
2번 물건	0	0	0	0	8	8	13	13
3번 물건	0	0	0	6	8	8	13	14
4번 물건	0	0	0	6	8	12	13	14

 

그런데 1차원 배열로도 풀 수 있다.

해당 배열을 n번 반복한다 했을때

n-1번째는 이전 상태이기 때문 또한 배열의 맨 마지막부터 해당 물건의 무게 까지 반복한다.(역순으로 채운다)

ex)

초기배열 dp

0

0

0

0

0

0

0

 

n = 0 

1번째 물건 선택

dp

0

0

0

0

0

0

13

13

n = 1

1~2번째 물건 선택

dp

0

0

0

0

8

8

13

13

n = 2

1~3번째 물건 선택

dp

0

0

0

6

8

8

13

14

n = 3

1~4번째 물건 선택

dp

0

0

0

6

8

12

13

14

 

 

n, k = map(int, input().split())
item = list()

for _ in range(n):
    item.append(tuple(map(int, input().split())))

##################
# 1차원 배열 풀이
dp2 = [0] * (k+1)
for i in range(n):
    for j in range(k, item[i][0]-1, -1):
        dp2[j] = max(dp2[j], dp2[j-item[i][0]] + item[i][1])

print(dp2[k])
##################

##################
# 2차원 배열 풀이
dp = [[0] * (k + 1) for _ in range(n)]

for i in range(n):
    for j in range(k + 1):
        if i == 0:
            if item[i][0] <= j:
                dp[i][j] = item[i][1]
        else:
            if j - item[i][0] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j - item[i][0]] + item[i][1], dp[i - 1][j])

print(dp[n - 1][k])
##################