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

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

cache[100][100001]에 어떤 인덱스에 어떤 무게일때 배낭에 넣을 수 있는 물건들의 가치의 최댓값 저장했다. 각 인덱스에서 해당 물건을 고를 때와 고르지 않을 때를 비교해서 문제를 풀었다.

 

코드

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

int n, k;
vector<pair<int, int>> item; //무게, 가치
int cache[100][100001]; //어떤 인덱스에 어떤 무게일때 배낭에 넣을 수 있는 물건들의 가치의 최대값 저장

void Pre()
{
	for (int i = 0; i < 100; i++)
		for (int j = 0; j < 100001; j++)
			cache[i][j] = -1;
}

int Solve(int index, int weight)
{
	if (weight > k) //버틸 수 있는 무게를 넘어갔을때
		return -987654321;

	if (index == n) 
		return 0;

	int& ret = cache[index][weight];

	if (ret != -1)
		return ret;

	//해당 인덱스의 물건을 고를때와 안고를때 비교
	ret = max(Solve(index + 1, weight + item[index].first) + item[index].second, Solve(index + 1, weight));

	return ret;
}

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

	Pre();

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		int w, v;

		cin >> w >> v;

		item.push_back(make_pair(w, v));
	}

	cout << Solve(0, 0);

	return 0;
}