배낭 (Knapsack) 알고리즘

물건을 최대 K 만큼 버틸 수 있는 배낭에 가장 가치가 높도록 물건을 구성했을때 가치의 최댓값을 구하는 알고리즘입니다.

그리드 알고리즘으론 정확한 답을 찾을 수 없어 동적 계획법으로 풀이하여야 합니다.

그리드 알고리즘으로 풀이를 할 경우엔 가장 높은 가치 순으로 탐색을 하였을 때
결과값 보다 더 높은 경우가 발생할 가능성이 있기 때문입니다.

따라서 동적 계획법으로 풀어야하는데
동적 계획법의 진행은 i번째 물건을 j무게까지 담을 수 있을 때 최댓값을 넣어 가면서 진행합니다.

그렇게 진행하면 물건이 중복되지 않고 무게를 갱신해 가면서 진행할 수 있습니다.

문제 출처 - 백준 12865번 평범한 배낭

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

위 물건들을 최대 무게 7 까지 버틸 수 있는 가방에 넣을 때 DP 진행 풀이입니다.

처음 무게 6인 물건을 넣었을때 DP 배열은

물건 ＼무게	1	2	3	4	5	6	7
6	0	0	0	0	0	13	13

입니다 테이블 안의 값은 가치입니다.

다음으로 무게 4인 물건을 넣으면

물건 ＼무게	1	2	3	4	5	6	7
6	0	0	0	0	0	6	6
4	0	0	0	8	8	13	13

위와 같이 됩니다. 6과 4는 같이 배낭에 넣을 수 없으니 각각 넣은 값만 들어갑니다.

물건 ＼무게	1	2	3	4	5	6	7
6	0	0	0	0	0	6	6
4	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14

무게 3인 물건을 넣었을 땐 처음으로 두 물건을 같이 넣을 수 있는 상황이 나타납니다.

무게가 최대 7인 상황까지 계산하였을 때 무게 3인 물건과 이전에 계산했던 무게 4(7-3)인 물건의 가치가 이전의 무게 7에 해당하는 값보다 크다면 합한 값으로 넣어줍니다.

식으로 표현하면 다음과 같습니다.

DP[ i ][ j ] = max ( DP[ i - 1 ][ j ], List[ i ]의 가치 + DP[ i - 1][ j - List[ i ]의 무게 ] )

마지막 무게 5인 물건까지 넣으면 다음과 같이 DP배열이 완성됩니다.

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

 

정리

점화식

if (nWeight <= j)
vDp[i][j] = max(vDp[i - 1][j], nValue + vDp[i - 1][j - nWeight]);
else
vDp[i][j] = vDp[i - 1][j];

풀이 코드

#include <vector>
#include <iostream>
#include <limits>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

int main()
{
	int nVal, nSize;
	cin >> nVal >> nSize;
	vector<vector<int>> vArr(nVal, vector<int>(2));
	vector<vector<int>> vDp(nVal, vector<int>(nSize + 1, 0));

	for (int i = 0; i < nVal; i++)
	{
		cin >> vArr[i][0] >> vArr[i][1];
	}

	int nMax = 0;
	for (int i = 0; i < nVal; i++)
	{
		int nWeight = vArr[i][0];
		int nValue = vArr[i][1];

		for (int j = 1; j <= nSize; j++)
		{
			if (i != 0)
			{
				if (nWeight <= j)
					vDp[i][j] = max(vDp[i - 1][j], nValue + vDp[i - 1][j - nWeight]);
				else
					vDp[i][j] = vDp[i - 1][j];
			}
			else
			{
				if (nWeight <= j)
					vDp[i][j] = nValue;
				else
					vDp[i][j] = 0;
			}
		}
	}

	cout << vDp[nVal - 1][nSize] << '\n';

	return 0;
}