[백준] 12865번 평범한 배낭(python 파이썬)

저번 시간에 배운 동적 프로그래밍 관련 문제를 하나 풀어보겠습니다!

 

문제

12865번: 평범한 배낭

 

사용한 알고리즘

- 동적 프로그래밍(dp)

 

 

아이디어

- 보석을 하나하나 추가했을 때의 배낭 무게별 최대가치를 계산

 

ex) 가방 최대 무게 : 7 

 

보석

보석 번호	무게	가치
0	6	13
1	4	8
2	3	6
3	5	12

이 때, 보석을 0번~3번 까지 하나하나 넣으면서 계산해 봅시다!

표의 값은 배낭 무게별 최대 가치입니다!

0 번째 보석 추가(무게 6 가치 13)

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	13	13

 

 

1번째 보석 추가(무게 4 가치 8)

	0	1	2	3	4	5	6	7
1	0	0	0	0	8	8	13	13
0	0	0	0	0	0	0	13	13

배낭의 무게가 6이상인 경우에는 0번째 보석만 넣는 것이 더 좋은 가치를 얻을 수 있습니다

 

2번째 보석 추가(무게 3 가치 6)

	0	1	2	3	4	5	6	7
2	0	0	0	6	8	8	13	14
1	0	0	0	0	8	8	13	13
0	0	0	0	0	0	0	13	13

무게가 7인 경우에는 1번째 2번째 보석을 넣는 것이 더 좋은 가치를 얻는 것을 확인할 수 있습니다.

 

3번째 보석 추가(무게 5 가치 12)

	0	1	2	3	4	5	6	7
3	0	0	0	6	8	12	13	14
2	0	0	0	6	8	8	13	14
1	0	0	0	0	8	8	13	13
0	0	0	0	0	0	0	13	13

 

 

규칙 발견

여기서 저희는 문제를 해결하는 방법에 대하여 알 수 있습니다.

k번째 보석을 넣기전인 k-1번째의 보석을 넣었을 때의 배낭 무게별 가치와 비교하고 있습니다.

k번째 보석의 무게가 w, 가치가 v 일 때,

k-1번째의 결과중 무게가 w 이상인 wi 값에 대하여 wi-w의 v(i-w)+w와 현재가치 vi을 비교하여 큰 값을 할당하고 있습니다.

이를 수식으로 표현하면 다음과 같습니다

dp[i] = max(dp[i], dp[i-w]+v) (단, i>=w)

 

전체 코드

import sys
input = sys.stdin.readline

N,K = map(int,input().split())
items = []
for _ in range(N):
    w,v = map(int,input().split())
    items.append((w,v))
dp = [0 for _ in range(K+1)]
for item in items:
    w,v = item
    for i in range(K,w-1,-1):
        dp[i] = max(dp[i],dp[i-w]+v)
print(dp[-1])

잘못된 내용이 있으면 피드백 부탁드립니다!

궁금한 내용이 있으면 언제든지 물어보세요!!!