[BOJ]12865 : 평범한 배낭(c++)

[문제] : https://www.acmicpc.net/problem/12865

[풀이]

물건의 무게와 가치를 저장해 놓은 배열의 인덱스를 증가시켜가면서 현재 물건을 가방에 넣을 수 있을 경우 가방에 넣는 경우와 가방에 넣지 않는 경우를 비교해 더 큰 쪽을 리턴하도록 재귀함수를 세웠다. 미리 물건의 무게를 기준으로 배열을 정렬시켜 만약 현재 물건을 가방에 넣었을때 무게가 초과되면 바로 리턴될수 있게 하였다.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>


using namespace std;

vector<pair<int, int>> Arr;
int cache[101][100001];
int N;
int K;

int DP(int idx, int weight)
{
	if (N <= idx) return 0;

	int& ret = cache[idx][weight];
	if (ret != -1) return ret;
	int ret1 = 0, ret2 = 0;
	if (weight + Arr[idx].first <= K)
	{
		ret1 += DP(idx + 1, weight + Arr[idx].first) 
			+ Arr[idx].second;
		ret2 += DP(idx + 1, weight);
	}
	else
	{
		return 0;
	}

	return ret = max(ret1, ret2);
}


int main(void)
{
	cin >> N >> K;
	Arr.resize(N);

	memset(cache, -1, sizeof cache);
	for (int i = 0; i < N; ++i)
	{
		int a, b;
		cin >> a >> b;

		Arr[i] = { a, b };
	}

	sort(Arr.begin(), Arr.end());

	cout << DP(0, 0) << endl;
}