[백준 C++] 12865 평범한 배낭 - 다이나믹프로그래밍

12865번: 평범한 배낭

#include <iostream>
using namespace std;

int DP[101][100001];

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

	int N, K;
	cin >> N >> K;

	for (int i = 1; i <= N; ++i)
	{
		int Weight, Value;
		cin >> Weight >> Value;

		for (int w = 0; w <= K; ++w)
		{
			if (Weight <= w)
			{
				DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - Weight] + Value);
			}
			else
			{
				DP[i][w] = DP[i - 1][w];
			}
		}
	}

	cout << DP[N][K];
}

---

 

물품의 정보를 입력받는 순서대로 하나씩 넣어보면서 이전까지의 최대값과 비교해보는 DP 문제입니다.

 

물품 하나를 입력받을 때마다 0부터 K까지 모든 무게의 경우마다 각각 현재까지의 최대가치를 저장해줍니다.

- 각 무게 상황마다 현재 물품을 넣었을 때와 넣지 않았을 때를 비교해서 둘 중 최대값을 저장

- 현재 물품을 넣지 않았을 때: DP[i - 1][w]

- 현재 물품을 넣었을 때: DP[i - 1][w - Weight] + Value

(Weight: 현재 물품의 무게, Value: 현재 물품의 가치)

 

예제를 예시로 DP 값을 저장하면 다음과 같은 형태의 배열이 완성됩니다.

i \ w	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

 

위쪽부터 아래쪽으로 한 행씩 테이블을 모두 채워주면, 가장 마지막에 채워진 값이 답이 됩니다.