Knapsack Problem

Knapsack Problem이란

주어진 용량을 초과하지 않으면서 물건의 가격이 최대가 되게 하는것이다.

다음과 같은 조건이 있다고 해보자.

배낭의 용량 : 15kg

물건 번호 (i)	물건 i의 가격	물건 i의 무게
1	$4	12kg
2	$2	2kg
3	$2	1kg
4	$1	1kg
5	$10	4kg

이 문제를 해결하기 위해 다음과 같은 알고리즘을 적용한다.

여기서 OPT는 다음과 같은 이중배열을 의미한다.

여기서 물건번호가 1인것부터 우측으로 채워나갈 것이다.

먼저 하나라도 index가 0이면 0으로 채워준 상태에서

만약 물건의 무게가 좌표에서 가르키는 무게보다 크다면 바로 위의 좌표의 값을 채워준다.

(채우고자 하는 무게보다 해당 물건의 무게가 무겁기 때문에 앞의 물건까지 채웠을 때 최댓값을 그대로 갖다 쓰는것이다.)

만약 좌표가 가르키는 무게가 물건의 무게보다 크거나 같다면 

해당 좌표의 무게일 때 앞의 물건까지 채웠을 때의 가치와

해당 물건의 무게를 뺀 상태에서 앞의 물건을 채웠을 때의 가치에서 해당물건의 가치를 더했을

때의 가치를 비교해주어 더 큰것을 넣어주는 식으로 진행한다.

결과는 다음과 같으며 만약 말로 설명한게 이해가 안된다면

알고리즘과 이 표를 함께 보면서 표가 채워져나가는 모습을 확인한다면

이해할 수 있을것이다.

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

이 사이트의 5215. 햄버거 다이어트 문제는 정확히 이 방식을 통해 해결할 수 있는 문제이다.

완벽한 이해를 위해 이 문제까지 한번 풀어보도록 하자.

아래는 풀이 소스이다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[21][10001];
int value[21];
int cal[21];
int main()
{
	int T;
	scanf("%d", &T);
	for (int i = 0; i < 21; i++) arr[i][0] = 0; //index가 0인 부분 초기화
	for (int i = 0; i < 10001; i++) arr[0][i] = 0; //index가 0인 부분 초기화
	for (int i = 1; i <= T; i++) {
		int N, L;
		scanf("%d %d", &N, &L);
		for (int j = 1; j <= N; j++) {
			scanf("%d", &value[j]);
			scanf("%d", &cal[j]);
		}

		for (int j = 1; j <= N; j++) { //knapsack 알고리즘
			for (int k = 1; k <= L; k++) {
				if (k < cal[j]) arr[j][k] = arr[j - 1][k];
				else {
					arr[j][k]= max(arr[j - 1][k], arr[j - 1][k - cal[j]] + value[j]);
				}
			}
		}
		printf("#%d %d\n", i, arr[N][L]);
	}
}