[알고리즘/C++] Knapsack problem(배낭 문제)

배낭 문제는 특정 무게와 가치를 갖는 물건들이 주어질 때 배낭의 무게 제한을 만족하면서 

 

가장 가치를 크게 하는 물건들의 조합을 찾는 전형적인 동적 계획법(Dynamic programming) 문제이다. 

 

int knapsack(vi weight, vi value, int limit) {
	vector<vi> ans(weight.size() + 1, vi(limit + 1, 0));

	int row = weight.size();
	int col = limit;

	weight.insert(weight.begin(), 0);
	value.insert(value.begin(), 0);
	//add sentinel value

	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			print2DVec(ans);
			cout << "\n";
			if (j >= weight[i]) {
				ans[i][j] = max(ans[i - 1][j], ans[i - 1][j - weight[i]] + value[i]);
				//바로 위 값(현재 아이템 추가X의 최대 가치)과
				//이전 행에서 현재 아이템을 추가했을 때의 가치를 비교
			}
			else {
				ans[i][j] = ans[i - 1][j];
			}
		}
	}

	return ans[ans.size()-1][ans[0].size()-1];
}

전체 코드는 위와 같다. 

 

int knapsack(vi weight, vi value, int limit) {
	vector<vi> ans(weight.size() + 1, vi(limit + 1, 0));

	int row = weight.size();
	int col = limit;

가치를 비교하기 위해서 (물건 개수 + 1, 무게 제한 + 1) 크기의 2차원 벡터를 만들어주고 0으로 초기화한다. 

 

행과 열에 1씩 크기를 늘린 이유는 구현의 편의를 위해서 패딩(padding)을 추가해준 것이다.

 

	weight.insert(weight.begin(), 0);
	value.insert(value.begin(), 0);
	//add sentinel value

그리고나서 weight와 value에 처음 값에 0을 추가해준다. 마찬가지로 구현의 편의를 위한 패딩값이다.

 

	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			if (j >= weight[i]) {
				ans[i][j] = max(ans[i - 1][j], ans[i - 1][j - weight[i]] + value[i]);
				//바로 위 값(현재 아이템 추가X의 최대 가치)과
				//이전 행에서 현재 아이템을 추가했을 때의 가치를 비교
			}
			else {
				ans[i][j] = ans[i - 1][j];
			}
		}
	}

각 행과 열을 순회하면서 물건을 담았을 때와 담지 않았을 때의 가치를 비교한다.

 

	vi weight = { 6, 4, 3, 5 };
	vi value = { 13, 8, 6, 12 };
	int limit = 7;

위의 예시에서 그 메카니즘을 살펴보자.

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

 

 

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

 

처음에 sum은 위의 형태로 초기화된다.

 

주황색으로 표시된 부분은 패딩으로 추가된 부분이고, 행은 물건의 경우를, 열은 무게제한을 나타낸다.

 

0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

 

가장 먼저 만나는 것이 무게 6의 가치 13인 물건인데 비교대상이 패딩된 값이므로 값이 그대로 들어간다. 

 

0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 13
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

 

그리고 다음 열도 마찬가지로 값이 채워진다. 같은 행에서 열이 끝까지 채워진다는 의미는 

 

열 자체가 무게 제한의 크기(+패딩)만큼 만들어졌기 때문에 

 

'이 물건들의 조합이 무게를 만족한다'는 의미가 된다. 

 

현재 같은 행에서 이루어지기 때문에 같은 물건에 대해서 고려되고 있다.

 

0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 13
0 0 0 0 8 8 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

 

그리고 다음 행(다음 물건 - 무게 4, 가치 8)에 대해서 고려할 때, 열이 계속 채워지다가

 

7번째 열에서 위의 행과의 진정한 비교가 이루어진다. 

 

바로 위 행의 물건의 무게와 만나는 지점이기 때문에 위의 행의 물건만(ans[i - 1][j]) 들고 가는 경우와

 

이전의 케이스에서 현재 물건도 같이 추가(ans[i - 1][j - weight[i]] + value[i])한 경우가 더 큰 지 비교한다.

 

0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 13
0 0 0 0 8 8 13 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

 

0에서 8이 더해진 8과 13을 비교했을 때, 13이 더 크므로 13으로 채워진다.

 

0이 갖는 의미는 '무게 제한이 2'일 때의 가능한 배낭의 케이스이다. 

 

물건 중에 가장 가벼운 것이 3이므로 불가능하므로 아무것도 들어갈 수 없다.

 

비교를 위의 행의 현재 물건의 무게만큼 열을 후퇴시킨 위치(x)의 값에서 현재 물건의 가치를 더해서 비교한다는

 

의미는 무게 제한이 x인 케이스에서 현재의 물건을 추가해보겠다는 것이다. 

 

이 물건을 추가해도 되는가? 아니면 바로 위의 행의 값(추가 안했을 때)이 차라리 더 큰가?의 비교를 통해 

 

이번 물건을 배낭에 담을지, 아니면 건너뛸지 결정한다. 

 

0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 13
0 0 0 0 8 8 13 13
0 0 0 6 8 8 13 14
0 0 0 0 0 0 0 0

 

세 번째 행의 물건(무게 3, 가치 6)의 경우이다. 위의 행에서 3(나의 무게)만큼 열을 후퇴시킨 케이스는

 

열이 4번째(패딩 제외)이므로 무게 제한이 4인 경우이다. 이 경우에는 과거 순회(1번째, 2번째 물건만 고려)상

 

2번째 물건만 들어갈 수 있기 때문에 그 케이스에 나의 물건을 더했을 때의 경우는 14의 가치를 가진다. 

 

이는 1번째 물건만 넣은 경우인 13보다 크게되므로 14가 들어간다. 

 

이런 메커니즘으로 모든 경우를 순회한 결과는 아래와 같다.

 

0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 13
0 0 0 0 8 8 13 13
0 0 0 6 8 8 13 14
0 0 0 6 8 12 13 14

 

	cout << knapsack(weight, value, limit);

결과는 14이다.

 

이와 같은 메커니즘의 동적 프로그래밍의 장점은 물건의 무게와 가치가 크기별로 정렬되어 있지 않고

 

뒤죽박죽이어도 동적 프로그래밍에 의해 비교가 이루어지면서 최선의 결과가 업데이트된다는 것이다.