[C++ 알고리즘] 다이나믹프로그래밍2 - 배낭문제(Knapsack Problem)

배낭문제(Knapsack Problem)

다이나믹 프로그래밍의 대표적인 예시문제이다. 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 아래와 같은 형식으로 주어진다.

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

12865번: 평범한 배낭

문제를 요약하자면 아래와 같다. 

짐 4개가 다음과 같이 있을 때, 7kg까지 넣을 수 있는 가방에 넣을 수 있는 짐의 가치의 최대합은 얼마인가?

무게	가치
6	13
4	8
3	6
5	12

사실 이 문제는 짐을 쪼갤 수 있는 경우와 쪼갤 수 없는 경우로 나눠진다. (위 문제의 경우 쪼갤 수 없는 경우) 짐을 쪼갤 수 있는 경우 그리디 알고리즘, 쪼갤 수 없는 경우에는 동적계획법(Dynamic Programming)을 이용해서 푼다. 이 글에서는 동적계획법을 이용해 푸는 방법에 대해 다루도록 하겠다.

 

아이디어

이차원 배열을 만들어 칸을 채워나가며 문제를 풀게 된다.

 

1. [짐의 수+1][무게+1] 크기의 배열을 생성한다. 위 문제의 경우 짐이 4개이고 가방에 7kg까지 담을 수 있으니 아래와 같이 표를 생성한다. 

 

2. 칸을 채워나간다. 우선 첫 번째 행의 경우는 가방에 무게6, 가치 13의 짐을 넣으려 하는 경우이다. 1~5kg까지 담을 수 있다고 가정하면 이 짐은 넣을 수 없고, 6,7kg까지 담을 수 있다고 하는 경우에만 짐을 넣을 수 있다. 따라서 표는 아래와 같이 된다. 

 

최대 7kg까지 담을 수 있다고 했기 때문에 두 번째 짐도 넣으면 표가 아래와 같이 될 것이다. 여기서 주목할 점은 배열[2][6] , 배열[2][7]부분이다. 가치 6짜리 짐을 넣는 것 보다 13짜리 짐을 넣는 것이 이득이기 때문에 바로 윗칸의 값, 즉 배열[1][6], 배열 [1][7]부분을 각각 가져오고 있다.

이제 3,6짜리 짐을 넣는다고 해보자. 여기서는 배열[3][7]부분에 주목해야 한다. 단순히 윗칸의 값을 가져오는 것보다 가치 8짜리 짐(2번 짐)과 가치 6인 짐(3번짐)을 넣는 것이 이득이기 때문에 값 14가 들어간다. 

 

즉 우리는 여기서 알고리즘의 점화식을 구할 수 있다. 경우는 아래와 같다.

짐을 넣는 경우는 바로 위의 경우를 보면 된다. 3번째 짐을 넣을지 말지 검토할 때 무게 7까지 넣을 수 있다면, 2번 짐(무게 4, 가치 8)의 짐을 넣고 3번 짐을 넣었다. 즉 배열[3][7]에 배열[2][7-3번짐의 무게(3)]+3번 짐의 가치(6) 값을 넣었다.

 

이제 표를 마저 채우면 아래와 같이 된다. 우리는 7kg까지 담을 수 있을 때의 최대 가치를 알고싶으니 배열[4][7]이 답이다. 즉 14가 답이 된다.

 

실제 코드(C++)

코드로 작성하면 아래와 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define P pair<int,int>
using namespace std;
//[물품 수][무게]
int arr[101][100001];
int allweight[101];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, k, w, v;
	cin >> n >> k;
	//(무게,가치)의 쌍을 담는 벡터 vv
	vector<P> vv;
	for (int i = 0; i < n; i++) {
		cin >> w >> v;
		vv.push_back(P(w, v));
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			int curweight = vv[i-1].first;
			int curval = vv[i-1].second;
			//현재 검토중인 짐을 담을 수 있는 경우(두 경우 중 최적의 경우 선정->max함수 사용)
			//1. 현재 짐을 넣지 않는다(바로 윗 칸의 값을 가져온다.) arr[i-1][j]
			//2. 현재 짐을 넣는다.arr[i-1][j-curweight]+curval
			if (curweight <= j) {
				arr[i][j] = max(arr[i - 1][j - curweight] + curval, arr[i - 1][j]);
			}
			//현재 검토중인 짐을 담을 수 없는 경우
			//바로 윗 칸의 값을 가져온다. arr[i-1][j]
			else {
				arr[i][j] = arr[i - 1][j];
			}
		}
	}
	cout << arr[n][k];

}

 

같이 풀면 좋은 문제(추가 예정)

배낭 문제의 대표적인 문제이다.

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

12865번: 평범한 배낭