[백준] 12865번 평범한 배낭

1. 문제

https://www.acmicpc.net/problem/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)가 주어진다.

최대 K만큼의 무게까지 넣을 수 있는 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 찾는 것이다.

2. 풀이

이 문제는 흔히 배낭 문제(Knapsack Problem) 이라 불리는 알고리즘의 일종이다.

배낭 문제는 두가지의 경우가 있는데 이 문제처럼 물건을 분할하지 못하는 0-1 배낭 문제와 분할하지 못하는 배낭 문제가 있다.

배낭 문제의 예시는

A 상자가 12KG, B상자가 5KG, C상자가 7KG 있고 각각의 상자에서 물건을 1KG씩 꺼낼수 있을때 담을 수 있는 최대 가치

같이 상자안의 내용물을 분할 할 수 있는 문제고 풀이는 그리디를 사용하여 풀 수 있다.

하지만 이 문제처럼 상자안의 내용물을 분할하여 담지 못하는 0-1 배낭 문제일 경우 그리디 알고리즘으로는 최적해를 찾을 수 없어 다른 방법을 찾아야한다.

나는 동적 계획법(DP)로 풀었다.

풀이는 N개의 물건을 하나씩 1부터 K 무게까지 넣을 수 있는 가치의 최대값을 기록하며 확인을 하면된다.

그래서 i는 N까지 물건에 대하여 반복문을 돌리고, 그안에서 j는 1부터 K까지 무게에 대해 반복문을 돌리며 아래 작업을 한다.

(1) 만약 물건 i를 현재 무게 j에 넣을 수 없다면,
이전 무게의 최대값이 현재 무게에서의 가치의 최대값이니 그대로 저장

(1) 만약 물건 i를 현재 무게 j에 넣을 수 있다면,
이전 무게의 최대값 vs 현재 물건 + 현재 물건을 뺀 무게에서의 가치의 최대값 을 비교하여 더 높은 가치를 저장

보기 쉽게 문제의 예시를 가지고 표를 그려 설명을 하면

4 7
6 13
4 8
3 6
5 12

예시가 주어졌을 때 물건은 총 4개, 가방에 담을 수 있는 무게는 7이다.

i는 4번, j는 1에서 7까지 반복문을 돌린다.

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

첫번째 물건은 무게 6에 13의 가치를 가지고 따라서 j가 6이 되었을 때 처음으로 가방에 넣을 수 있게된다.

세번째 물건에서 무게가 7일때를 확인해보면 비교를 하는데
이전 무게의 최댓값 13 vs 현재 물건의 가치 6 + 현재 물건의 무게를 뺀 무게에서의 최대값 8을 비교하여 최대값 14를 집어넣었다.

이런 방식으로 중간중간 저장을 하여 중복을 방지하는 방법을 메모이제이션 이라고 부른다.

3. 코드

#include <iostream>
#include <algorithm>
using namespace std;

int N, K, weight[101], value[101];
int dp[101][100001];

int main()
{
	cin >> N >> K;

	for (int i = 1; i <= N; ++i)
	{
		int w, v;
		cin >> w >> v;
		weight[i] = w;
		value[i] = v;
	}

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= K; ++j)
		{
			if (j - weight[i] >= 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
			else dp[i][j] = dp[i - 1][j];
		}
	}

	cout << dp[N][K];
}

4. 후기

나를 괴롭혀주는 알고리즘 공부의 친구 DP다.
오늘도 DP가 DP했다. DP는 사실 풀이 방법론이고 때문에 이를 활용하는 알고리즘 풀이가 매우 많으니 꾸준히 풀어보고 공부해야겠다는 생각이 들었다.