[백준 파이썬] 12865 평범한 배낭

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

12865번: 평범한 배낭

문제

가방과 물건의 정보가 주어지고 물건을 선택했을 때 가장 가치가 높은 경우의 수를 출력하는 문제이다

---

 

아이디어

DP로 풀면 되겠다고 생각했지만 아이디어가 떠오르지 않아 찾아보니 냅색 알고리즘이라는게 있었다.

냅색 알고리즘에 의하면 물건과 가치를 저장하는 2차원 배열을 생성한 뒤 배열을 탐색하며 가치를 저장해 배열의 마지막 인덱스를 출력하면 그것이 가장 큰 가치를 갖는 경우가 된다.

---

풀이

먼저 가방의 무게와 물건의 개수만큼의 2차원 배열을 생성한다.

dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

 

예제를 이용하면 다음과 같은 배열이 나온다.

	가방의 무게	1	2	3	4	5	6	7
물건의 개수	0	0	0	0	0	0	0	0
1번 물건	0	0	0	0	0	0	0	0
2번 물건	0	0	0	0	0	0	0	0
3번 물건	0	0	0	0	0	0	0	0
4번 물건	0	0	0	0	0	0	0	0
5번 물건	0	0	0	0	0	0	0	0

이 배열의 각각의 값은 행을 w 열을 i 라고 했을 때

w의 무게를 가진 가방을 i번째 물건까지 넣었을 때 가지는 최대 가치가 된다

 

 

가방에 물건을 넣는 경우의수는 다음과 같다.

1. 물건을 넣지않는 경우

2-1. 물건을 넣는경우

2-2. 다른 물건을 빼고 현재 물건을 넣는경우

 

1번의 경우는 다음과 같은 조건을 건다.

if j < weight:
            dp[i][j] = dp[i - 1][j]

이는 현재의 물건의 무게가 배낭의 최대무게를 초과했을 경우이다.

이 경우는 애초에 물건을 넣을 수 없으므로 이전 물건dp[i-1]의 최대가치 dp[i-1][j]를 가져온다.

 

2-1과 2-2는 두 경우를 비교해서 큰값을 가지는 경우를 선택하면된다.

dp[i][j] = max(value + dp[i - 1][j - weight], dp[i - 1][j])

 

value + dp[i - 1][j - weight]은 물건을 넣는경우이고

dp[i-1][j]는 물건을 넣지 않았을 경우이다.

 

이 때 j-weight을 하는 경우는 물건이 들어갈 공간을 확보하기 위해서이다. i-1(이전 물건을 넣는경우)의 j-weight(현재 물건을 넣을 공간을 확보한 경우)의 값에서 value값을 더한것이다.

그렇게 배열을 순회하고 배열의 끝을 출력하면 된다.

 

해당 배열을 표로 만들면 다음과 같다.

		0	1	2	3	4	5	6	7
weight	value
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	6	8	12	13	14

 

---

코드

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


backpack = [[0,0]]
for _ in range(N):
    backpack.append(list(map(int, input().split())))

dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, K + 1):
        weight = backpack[i][0]
        value = backpack[i][1] 

        if j < weight:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(value + dp[i - 1][j - weight], dp[i - 1][j])


print(dp[N][K])