[C++] 백준 12865번-평범한 배낭

BOJ 12865-평범한 배낭

문제

예제 입력

4 7
6 13
4 8
3 6
5 12

에제 출력

14

풀이

DP를 이용하는 냅색(Knapsack)문제다.

• 물건을 넣는 경우와 안넣는 경우 두가지에 대한 모든 경우의 수 중 무게가 k보다 안 높고 value가 가장 높은 경우를 구한다.
• 필요없는 경우의 수를 제외하기 위해 flag[무게 합][탐색 중인 배낭 Index]의 값에 가장 높은 value값을 저장하고 만약 이 값보다 낮으면 탐색을 중단한다.

소스코드

#include "bits/stdc++.h"
using namespace std;

int n, k;
int weight[101];
int value[101];
int flag[100001][101];

int DP(int x, int w, int v) {
	if (w > k)
		return -1;
	if (x == n) {
		return v;
	}
	if (flag[w][x] != 0 && flag[w][x] >= v)
		return -1;
	flag[w][x] = v;
	int val = v;
	val = max(val,DP(x + 1, w, v));
	val = max(val,DP(x + 1, w + weight[x], v + value[x]));
	return val;
}

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

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> weight[i];
		cin >> value[i];
	}
	cout << DP(0, 0, 0);
}