(백준/C++) 12865_평범한 배낭

12865번: 평범한 배낭 문제는 동적 계획법 문제로, 무게가 k인 배낭에 최대한 가치있는 물건을 넣을 수 있는 최적 해를 찾는 문제입니다.

동적 계획법(Dynamic Programming, DP)이란, 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다.

우선, 동적 계획법 문제는 최적 부분 구조와 중복된 부분 문제의 두 가지 속성을 가집니다. 이 문제도 최적 부분 구조와 중복된 부분 문제에 대해 먼저 생각해보겠습니다.

1. 최적 부분 구조: 최적 부분 구조는 큰 문제의 최적 해가 작은 부분으로 나눈 하위 문제의 최적 해로부터 구성될 수 있는 것을 말합니다.
   우선 이 문제는 현재 물품을 배낭에 넣을지 말지 결정하는 것이 하나의 작은 문제가 될 수 있습니다.
   만약, 무게가 k인 배낭에 대한 최적 해를 안다면 무게가 k + w에 대한 최적 해도 구할 수 있습니다.
2. 중복된 부분 문제: 중복된 부분 문제는 큰 문제를 작은 부분으로 나눌 때 동일한 하위 문제가 여러 번 발생함을 의미합니다.
   이 문제에서 같은 물품을 여러 번 고려해야 할 수 있고, 같은 무게의 배낭을 여러 번 고려해야 할 수 있습니다.

---

접근법

1. 최적해를 담는 배열 선언

우선, 무게가 k인 배낭에 대한 최적 해를 저장하기 위해 배열을 선언할 수 있습니다.

여기에는 무게가 k인 배낭에 넣을 수 있는 최대 가치가 저장됩니다.

2. 물품을 하나씩 넣어보기

그 다음은 물품을 하나씩 넣어보며 최적해를 구해야 합니다.

이때, 현재 물건을 넣거나 넣지 않았을 때의 최대 가치가 높은 쪽을 구해야 합니다. 또한 무게가 w인 물건을 넣는 방법은 무게 w를 버틸 수 있는 k의 배낭에 넣을 수 있습니다. (w보다 큰 k의 배낭에는 다 넣어볼 수 있습니다.)

이렇게 모든 물품을 다 넣어보다 보면 최적해를 구할 수 있습니다.

---

풀이

1. 물품을 넣는 방법

무게 w를 버틸 수 있는 배낭 k에 물품을 하나씩 넣어보기 위해서는 우선 무게별로 정렬해주는 것이 좋습니다.

무게가 가벼운 물품부터 넣든 무거운 물품부터 넣든 일정한 순서대로 넣어야 탐색이 쉽기 때문입니다.

이때, 무게가 가벼운 물품부터 넣으려면 똑같은 물품이 여러번 들어가지 않도록 주의해야 합니다.

저 같은 경우에는 무게가 무거운 물품부터 넣었습니다.

이때에는 현재 무게 이상의 배낭에만 현재 물품에 대한 가치가 들어갑니다.

예를 들어, 무게 6 가치 13인 물품을 넣기 위해서는 무게 6 이상의 배낭에만 들어갑니다.

2. 이전 최적해와 물품을 넣었을 때의 해를 비교하기

물품을 넣을 때, 현재 물품의 가치만 계산해서는 안됩니다.

최적해를 구하기 위해서는 현재 물품의 무게를 제외한 나머지 무게의 배낭에 들어갈 수 있는 최적해에 대한 계산을 해줘야 합니다.

예를 들어, 무게 7의 배낭에 무게 6의 물품을 넣을 때, 무게가 1이 남기 때문에 무게 1인 배낭에 들어 갈 수 있는 최적 해를 더해줄 수 있습니다.

같은 방식으로 반복하다보면, 무게 7인 배낭에 무게 3인 물품을 넣을 때, 무게가 4가 남기 때문에, 무게가 4인 배낭에 들어갈 수 있는 최적 해인 8이 더해져 최종 결과가 14가 나옵니다.

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

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

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

	vector<pair<int, int>> thing(N);
	int value[100001] = { 0, };

	for(int i = 0; i < N; i++)
	{
		cin >> thing[i].first >> thing[i].second;
	}

	sort(thing.begin(), thing.end(), greater<pair<int, int>>());

	//모든 물품에 대해 탐색을 한다.
	for(int i = 0; i < N; i++)
	{
		//현재 무게까지의 최적 해를 탐색한다.
  		for(int j = K; j >= thing[i].first; j--)
		{
			//이전에 구한 최적해들에 대해서 현재 물품을 추가하거나 추가하지 않았을 때의 최적해를 다시 구한다.
			value[j] = max(value[j], value[j - thing[i].first] + thing[i].second);
		}
	}

	cout << value[K];
}