[백준] 12865번 - 평범한 배낭 (파이썬, C++)

문제) 백준 - 동적 계획법 (Dynamic Programming) - 평범한 배낭

-> www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

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

 

(물건 무게, 가치)가 (3, 4)인 경우를 주목하자.

1. 가방의 무게를 1부터 7까지 늘려가며 (3, 4)를 넣어준다.

2. 1과 2는 물건 무게보다 작으므로 이전 무게를 채택한다.

3. 3부터 7까지는 물건을 넣은 뒤 남은 무게로 채울 수 있는 값과 이전 최댓값을 위의 행에서 가져온다.

4. 둘의 최대를 비교한다.

 

점화식 : dp[ i ][ j ] = max( dp[ i - 1][ j ], dp[ i - 1 ][ j - weight_value[ i ][ 0 ] ] + weight_value[ i ][ 1 ])

 

 

Python 소스 코드)

 

 

2021/6/8 Update

---

 

C++소스 코드)

 

각 물건에 대해 물건을 넣을지, 안넣을지에 대한 경우의 수에서 물건들의 가치의 합을 계산한다. 완전탐색으로 구현할 경우, 시간복잡도는 O(2^n)이므로 시간 제한에 걸린다. 따라서 memoization을 통해 가방에 용량이 capacity만큼 남았을 때, item 이후 물건들을 넣어 얻을 수 있는 가치의 최대를 구한다.

 

 

ps. 2차원 배열보다 이해가 훨씬 쉬운듯하다...킹만북