[백준] 12865번 : 평범한 배낭

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 물건의 개수가 n개이고 최대 무게가 k일 때의 최대 가치 합을 구하기 위해 최대 무게가 1~k일 때에 대해 물건의 개수가 각각 1~n개인 경우의 최대 가치 합을 2차원 배열인 dp에 갱신하는 Bottom-Up 방식으로 풀었다.

1) 물건의 개수와 최대 무게를 입력 받아 저장하고, 각 물건들의 무게와 가치를 입력 받아 stuffs 벡터에 저장한다.

2) 2차원의 dp 배열의 0번째 행과 0번째 열은 전부 0으로 초기화한다. (물건의 개수가 0개일 때와 최대 무게가 0일 때는 모두 물건을 넣을 수 없으므로 최대 가치도 0)

3) dp 배열을 물건 개수가 i(1~n)일 때 최대 무게가 j(1 ~ k)인 경우 각각에 대해 갱신한다.

• dp[i][j] 에는 i번째 물건까지 있고, 최대 무게가 j일 때의 최대 가치가 저장된다.
  • 만약 현재 물건의 무게가 현재 최대 무게를 넘을 때 (stuffs[i].weight > j)
    • 가방에 넣을 수 없는 경우이므로 같은 최대 무게일 때 직전 물건까지의 최대 가치로 갱신
  • 만약 현재 물건의 무게가 현재 최대 무게를 넘지 않을 때 (stuffs[i].weight <= j)
    : 아래 두 가지 경우 중 더 큰 값으로 갱신
    • 현재 물건만큼의 무게를 확보하기 위해 다른 물건 빼고 현재 물건 넣을 때의 최대 가치
    • 현재 물건 넣지 않고, 같은 최대 무게일 때 직전 물건까지의 최대 가치
  • 이를 점화식으로 표현하면
    • if ((stuffs[i].weight > j) dp[i][j] = dp[i - 1][j]
    • else dp[i][j] = max(dp[i - 1][j - stuffs[i].weight] + stuffs[i].value, dp[i - 1][j])

4) dp[n][k]를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
typedef pair<int, int> pii;

vector<pii> stuffs;		// 각 물건들의 (무게, 가치) 저장
int dp[101][100001];	// dp[i][j] : i번째 물건까지 있고, 무게 제한이 j일 때의 최대 가치 합
int n, k;

int solution()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= k; j++)
		{
			if (stuffs[i].first > j)		// 현재 물건의 무게 > 현재 최대 무게 : 가방에 넣을 수 없는 물건이므로, 같은 최대 무게일 때 이전 물건까지의 최대 합 사용
				dp[i][j] = dp[i - 1][j];
			else                            
				dp[i][j] = max(dp[i - 1][j - stuffs[i].first] + stuffs[i].second, dp[i - 1][j]);	
				// 현재 물건의 무게 <= 현재 최대 무게 : 가방에 넣을 수 있는 물건이므로 두 가지의 경우 중 큰 값 사용
				// 1. 최대 무게가 (현재 최대 무게 - 현재 물건의 무게)이고 이전 물건까지 있을 때의 최대 가치 + 현재 물건의 가치 -> 현재 물건만큼의 무게 확보하기 위해 다른 물건 빼고 현재 물건 넣은 경우
				// 2. 같은 최대 무게일 때 이전 물건까지의 최대 합 -> 현재 물건 넣지 않은 경우
		}
	}
	return dp[n][k];
}

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

	cin >> n >> k;

	stuffs.push_back(pii(0, 0));	// 첫 물건의 인덱스를 1로 시작하기 위해 stuffs의 0번 인덱스 채워주기
	for (int i = 0; i < n; i++)
	{
		int w, v;
		cin >> w >> v;
		stuffs.push_back(pii(w, v));
	}
	cout << solution();
}