[BOJ] 12865. 평범한 배낭

Jimeaning·2023년 11월 9일

DP 냅색

코딩테스트

목록 보기

128/143

Python3

문제

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

키워드

냅색 알고리즘
DP

문제 풀이

문제 요구사항

N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다.
배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주는 프로그램.

변수 및 함수 설명

N: 물품의 수 (1 ≤ N ≤ 100)
K: 버틸 수 있는 무게 (1 ≤ K ≤ 100,000)
W: 물건의 무게 (1 ≤ W ≤ 100,000)
V: 물건의 가치 (0 ≤ V ≤ 1,000)

arr: 물건의 무게와 가치가 저장되는 2차원 리스트
dp: 최대 가치를 저장하는 리스트

풀이

물건	1	2	3	4
무게	6	4	3	5
가치	13	8	6	12

위와 같이 물건의 무게와 가치가 주어졌다고 하자.

아래 표는 물건의 무게별 최대 가치를 나타내는 표이다.
행은 물건의 번호를 의미하고, 열은 가방의 최대 무게를 의미한다.
표 내부 칸은 해당 물건의 무게까지 가질 수 있는 최대 가치를 의미한다.

1) 물건을 넣지 않았을 때

	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0	0	0	0
물건 1 (6kg)
물건 2 (4kg)
물건 3 (3kg)
물건 4 (5kg)

물건의 최대 가치는 0이다.

2) 물건 1만 넣었을 때

	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0	0	0	0
물건 1 (6kg)	0	0	0	0	0	0	13	13
물건 2 (4kg)
물건 3 (3kg)
물건 4 (5kg)

물건 1은 6 kg이기 때문에 6kg 이후부터 가치 13이 채워진다.
물건 1만 넣는다고 가정했으므로 7kg가 되었을 때도 가치는 13이다.

3) 물건 1, 2를 넣었을 때

	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0	0	0	0
물건 1 (6kg)	0	0	0	0	0	0	13	13
물건 2 (4kg)	0	0	0	0	8	8	13	13
물건 3 (3kg)
물건 4 (5kg)

물건 2가 들어왔을 때 4kg부터 가치가 8 채워진다.
6kg 이후부터는 물건 1도 들어올 수 있는데 가치가 1이 더 크므로 13으로 채워준다.

4) 물건 1, 2, 3을 넣었을 때

	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0	0	0	0
물건 1 (6kg)	0	0	0	0	0	0	13	13
물건 2 (4kg)	0	0	0	0	8	8	13	13
물건 3 (3kg)	0	0	0	6	8	8	13	14
물건 4 (5kg)

물건 3은 3kg이므로, 3kg에 6으로 채워준다.
가방에 넣을 수 있는 무게가 7kg가 되었을 때, 물건 1의 가치(13)보다 물건 2+물건 3의 가치(8+6 = 14)가 더 크므로, 14를 채워준다.

5) 물건 1, 2, 3, 4 넣었을 때

	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0
물건 1 (6kg)	0	0	0	13	13
물건 2 (4kg)	0	8	8	13	13
물건 3 (3kg)	6	8	8	13	14
물건 4 (5kg)	6	8	12	13	14

물건 4는 5kg이므로, 가방에 넣을 수 있는 무게가 5kg일 때부터 넣을 수 있다.
이때 물건 4(12)의 가치가 물건 2(8)의 가치보다 크기 때문에 12을 채워준다.

일련의 과정을 점화식으로 표현하면,,

$dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i)$

$v_i$ : 물건의 가치
$w_i$ : 물건의 무게
$dp[i][j]$ : 최대 이윤 ( $i$ : 현재 넣은 물건의 번호, $j$ : 넣을 수 있는 최대 무게)

최종 코드

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

arr = [[0, 0]]
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for _ in range(n):
    arr.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, k+1):    
        w = arr[i][0]
        v = arr[i][1]

        # 가방에 못 넣을 때
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

print(dp[n][k])