DP (배낭 문제)

1. 특징

---

배낭 문제 유형의 경우, 특정 스텝을 나아가는 도중에 "제약조건" 을 가지고 있어서 해당 조건을 체크해주는 작업이 필요하다.

 

예를 들어,

• 물건들을 고르는 방법의 수를 구하는데 "최대 무게"가 정해져 있음
• 동전을 모으는 방법의 수를 구하는데 "최대 금액" 이 정해져 있음
• 인사를 하면서 얻는 기쁨을 구하는데 "최대 체력"이 정해져 있음 

 

그렇기 때문에, 이중 for문을 사용해야 하는 경우가 많다.

• step을 밟아 나가는 for문
• 제약조건을 지켜주는 for문

 

2. 예시

---

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

 

이 문제는 가장 스탠다드한 형태의 문제이다.

• 바깥 for문을 통해 step을 밟아 나가면서
• 안쪽 for문을 통해서 제약조건을 지켜준다.

#include <iostream>
using namespace std;

int n;
pair<int, int> board[22];
int dp[22][102]; //현재 i번째 왔을때 남은 체력 j 일때의 기쁨
int answer = 0;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> board[i].first; //체력
	}
	for (int i = 1; i <= n; ++i)
	{
		cin >> board[i].second; //기쁨
	}
	
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 100; j >= 0; --j)
		{
			if (j - board[i].first > 0)
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - board[i].first] + board[i].second);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
			answer = max(answer, dp[i][j]);
		}
	}

	cout << answer;
}

 

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

 

이 문제는 가장 기본적인 배낭문제이다.

• 위의 문제와 같은 방식으로 풀 수 있다.

#include <iostream>
using namespace std;

int n, k;
pair<int, int> props[102];
int dp[102][100'002];
int answer = 0;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;

	for (int i = 1; i <= n; ++i)
	{
		int w, v;
		cin >> w >> v;

		props[i].first = w;
		props[i].second = v;
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 0; j <= k; ++j)
		{
			//넣을 수 있다면,
			if (j + props[i].first <= k)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + props[i].first] + props[i].second);
			else
				dp[i][j] = dp[i - 1][j];

			answer = max(answer, dp[i][j]);
		}
	}
	cout << answer;
}

 

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

이 문제는 조금 다른 방식으로 풀이를 했다. 

#include <iostream>
using namespace std;

int t;
int coins[22];
int dp[10002];

//n개의 동전으로 m 만들기
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> t;

	while (t--)
	{
		int n;
		int m;
		int answer = 0;

		cin >> n;

		fill(coins, coins + 22, 0);
		fill(dp, dp + 10002, 0);

		for (int i = 1; i <= n; ++i)
		{
			cin >> coins[i];
		}
		cin >> m;
		dp[0] = 1;

		for (int i = 1; i <= n; ++i)
		{
			for (int j = coins[i]; j <= m; ++j)
			{
				dp[j] += dp[j - coins[i]];
			}
		}
		cout << dp[m] << "\n";
	}

}

 

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

위 문제와 거의 유사한 문제

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

int n, k;
int value[102];
int dp[100'002];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;

	for (int i = 0; i < n; ++i)
	{
		cin >> value[i];
	}
	sort(value, value + n);
	dp[0] = 1;
	for (int i = 0; i < n; ++i)
	{
		for (int j = value[i]; j <= k; ++j)
		{
			dp[j] += dp[j - value[i]];
		}
	}
	cout << dp[k];
}