BOJ 12865 - 평범한 배낭

기본 knapsack문제다.

 

int knapsack(int pos, int cap) // 가방의 남은 용량이 cap이고 pos~n-1번 물건을 고를 때 가치의 최대.

0번 물건~ n-1번 물건을 순서대로 참조하면서

 1. pos번째 물건을 선택할 수 있을 경우 (물건의 무게가 cap보다 낮거나 같은 경우)

   ret = max(pos번째 물건을 선택하지 않은 경우, pos번째물건의 가치 + knapsack(pos+1, cap - item[pos].first)

 2. pos번째 물건이 너무 무거워 선택할 수 없는 경우

   ret = pos번째 물건을 선택하지 않은 경우

 

d[pos][cap]을 메모하며 dp하는 문제다.

 

 

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

int n, k;
int d[101][100001];
pair<int, int> item[101];

int knapsack(int pos, int cap) { //pos부터 골랐을 떄 가치의 최대
	//기저
	if (pos == n) return 0;
	if (d[pos][cap] != -1) return d[pos][cap];

	int ret;
	//pos번쨰 item 고를 수 있을 떄
	if (cap >= item[pos].first) 
		ret = max(knapsack(pos + 1, cap), item[pos].second + knapsack(pos + 1, cap - item[pos].first));
	else 
		ret = knapsack(pos + 1, cap);

	return d[pos][cap] = ret;
}

int main() {
	cin >> n >> k;
	for (int i = 0, w, v; i < n; i++) {
		cin >> w >> v;
		item[i] = { w,v };
	}
	fill(&d[0][0], &d[100][100001], -1);
	cout << knapsack(0, k) << '\n';
}