[lv3] 12865. 평범한 배낭(Python 파이썬 풀이, DP)

출처

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

12865번: 평범한 배낭

결과

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력

4 7
6 13
4 8
3 6
5 12

예제 출력

14

해석

1. BFS ( 시간 초과 )

가방의 무게 순서로 정렬을 한 이후에 무게가 낮은 것부터 차근차근 하나씩 넣는 방식으로 풀었습니다. 낮은 것부터 넣기 때문에 만약 최대 무게보다 무거운 물건이 들어온다면 더 이상 안 넣어도 되기 때문에 break를 걸면 쉽게 풀릴 수 있다고 생각하였지만, 물건은 최대 100개 이므로 최대 경우의 수가 100!로 제출을 하면 시간 초과가 뜨게 됩니다. 풀이는 아래와 같았고 새로운 풀이가 필요합니다.

import sys
 
def most_value(idx, w, v):
    global answer, n, k
    if v > answer:
        answer = v
    for i in range(idx, n):
        if w + li[idx][0] > k:
            return
        most_value(i+1, w + li[idx][0], v + li[idx][1])
 
n, k = map(int, sys.stdin.readline().split())
li = sorted(list(list(map(int, sys.stdin.readline().split())) for _ in range(n)), key=lambda x:x[0])
answer = 0
for i in range(n):
    most_value(i+1, li[i][0], li[i][1])
print(answer)

2. DP(동적 계획법)

이전에 계산한 값을 바탕으로 계산을 하는 DP방식으로 풀이를 하였습니다. 장점은 정렬을 할 필요가 없으며, 가방의 무게를 기준으로 풀이하기 때문에 최대 무게(100,000) X 물품의 수(100) 으로 106 가지로 100!보다는 시간 복잡도가 감소하였습니다.
풀이 방식은 가방의 무게가 1인 것부터 K까지인 가방을 준비하여 새로운 물건을 하나씩 넣을 때 마다 넣었을 때와 안 넣었을 때의 최대 가치 값들을 비교하는 것입니다.
예시로 입력값이
2 10
6 6
4 4
으로 주어진다면 무게가 1부터 10까지의 가방을 준비합니다. (처음에는 아무 물건이 없다는 의미로 무게와 가치가 0인 값을 넣을 때를 가정하여 각 값에 0을 넣습니다.)

무게	1	2	3	4	5	6	7	8	9	0
0	0	0	0	0	0	0	0	0	0	0

이제 한 개씩 물건을 넣습니다. 첫 번째 물건은 무게가 6이므로 6이상의 가방에는 가치가 6이 됩니다.

무게	1	2	3	4	5	6	7	8	9	0
0	0	0	0	0	0	0	0	0	0	0
(6, 6)	0	0	0	0	0	6	6	6	6	6

이제 4, 4인 물건을 추가합니다.

무게	1	2	3	4	5	6	7	8	9	0
0	0	0	0	0	0	0	0	0	0	0
(6, 6)	0	0	0	0	0	6	6	6	6	6
(4, 5)	0	0	0	5	5	6	6	6	6	11

위 처럼 무게가 4인 가방부터는 가치가 5인 물건이 들어갈 수 있으므로 가치가 5가 됩니다. (무게가 4인 물건 넣음)
하지만, 6인 가방부터는 이전의 값인 6이 더 높으므로 가치가 6이 됩니다. (무게가 4인 물건을 안 넣음)
마지막에 무게가 10인 가방에서는 무게가 6인 물건과 4인 물건이 들어갈 수 있습니다. 다시 말해, 아직 무게가 4인 물건을 넣지 않았을 때의 최대 가치에서 무게가 4인 가치를 합했을 때의 값(무게가 4인 물건을 넣었을 때)과 무게가 4인 물건을 넣지 않았을 때의 값을 비교하여 최대값을 구하면 됩니다.
값은 계속 최대값을 나타내므로 마지막 값만 출력하면 정답입니다.

소스 코드

import sys
 
n, k = map(int, sys.stdin.readline().split())
li = list(list(map(int, sys.stdin.readline().split())) for _ in range(n))
ba = list(list(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):
        if j >= li[i-1][0]:
            ba[i][j] = max(ba[i-1][j], ba[i-1][j - li[i-1][0]] + li[i-1][1])
        else:
            ba[i][j] = ba[i-1][j]
print(ba[-1][-1])