BOJ 12865 평범한 배낭

이 문제는 N개의 물건중 몇개를 골라서 그 고른 물건의 무게가 K보다 작거나 같게 하였을때 얻을수 있는 가치의 최댓값을 구하는 문제이다. 

처음 문제를 보았을때 물건을 무게순으로 정렬하여 모든 케이스에 대해 전부 탐색을 할까 생각했다. 

하지만 이렇게 풀었을때 O(n!)의 시간 복잡도가 나오게 된다. 예를 들어 n이 100이라고 하였을때 1개를 선택해서 그 가치가 최대가 될수 있지만 100개를 전부 선택을 해야 가치가 최대가 될수 도 있다. 따라서 각각의 경우에 최악의 경우 100,99,98...개를 선택해야하는 경우가 발생한다.

 

 이 문제를 해결하기 위해 2차원 배열 dp[i][k]를 생성하고 i는 n개의 물건중 i번째 물건을 선택한경우, k는 무게 제한으로 1부터 k 까지 모든 경우에 dp를 채워나가면 된다.

예를들어 dp[1][1]은 최대로 버틸수 있는 무게가 1이고 이때 1번째 물품을 선택하였을때 얻을수 있는 최대 가치를 의미한다.

 

문제 예시에서 w={6,4,3,5}, v={13,8,6,12} 이고 dp[1][0] = 0, dp[2][0]=0, dp[3][0]=0, dp[4][0]=0이 된다.

그렇다면 하나씩 가치를 구해보자.

k=1일때

dp[1][1]은 w[1]이 6 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

dp[2][1]은 w[2]이 4 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

dp[3][1]은 w[3]이 3 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

dp[4][1]은 w[4]이 5 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

 

K=2일때

dp[1][2]은 w[1]이 6 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

dp[2][2]은 w[2]이 4 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

dp[3][2]은 w[3]이 3 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

dp[4][2]은 w[4]이 5 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

 

K=3일때

dp[1][3]은 w[1]이 6 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

dp[2][3]은 w[2]이 4 이므로 k범위를 넘어가게 되고 가치는 0이 된다.

dp[3][3]은 w[3]이 3 이므로 k범위안에서 물건을 선택 할 수 있다. 따라서 가치는 v[3]인 6이 된다.

이때 생각해 줘야하는 부분은 이전의 물건을 선택했을때 가지와, 새롭게 추가되는 가치를 비교해서 더 큰값을 넣는다는 것이다. 예를들어 dp[2][3]은 현재 2번째 물건을 선택 하거나 하지 않았을때 얻을수 있는 가치의 최댓값을 의미한다. 만약에 3번째 물건을 선택한다면 얻을수 있는 가치는 6이지만 현재 무게 제한에서 3번째 물건을 선택하고 남은 무게 제한에 대해 가치를 더한 값이 최종적으로 얻을수 있는 가치가 된다.

정리 하자면 dp[i][k] = max(dp[i-1][k-w[i]]+v[i],dp[i-1][k]) 가 된다.

 

이런 점화식을 도출하는것이 꽤 어려웠고 나도 다른분 풀이및 설명을 참고하여 문제를 풀었다.

참고

[C++] 백준 12865번 - 평범한 배낭 (자세한 설명, DP, Knapsadck Problem)

최종 코드는 다음과 같다.

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

int v[101] = { 0, };
int w[101] = { 0, };
int dp[101][100001];
int n, k;

void solution()
{
	for(int i = 1; i <= n; i++)
	{
		cin >> w[i] >> v[i];
	}

	//초기화
	for(int r = 0; r <= n; r++)
	{
		dp[r][0] = 0;
	}
	for(int c = 0; c <= k; c++)
	{
		dp[0][c] = 0;
	}

	for(int limit = 1; limit <= k; limit++)
	{
		for(int row = 1; row <= n; row++)
		{
			if(w[row] > limit)
			{
				dp[row][limit] = dp[row - 1][limit];
			}
			else
			{
				dp[row][limit] = max(dp[row - 1][limit - w[row]] + v[row], dp[row - 1][limit]);
			}
		}
	}

	cout << dp[n][k];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	memset(dp, 0, sizeof(dp));

	cin >> n >> k;
	solution();
}