백준 12865번 평범한 배낭 C/C++ 풀이

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

가장 고전적인 DP 문제

 

예전에는 DP를 점화식으로만 이해했었는데, 2차원 배열로 이해하고 나니 더 깊은 이해를 할 수 있게 되는 것 같다.

 

https://gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

아래는 알고리즘을 설명하는 블로그 글

 

#include <cstdio>
#include <memory.h>
#include <algorithm>

using namespace std;

FILE* in = fopen("input.txt", "r");

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

//재귀함수로 구현한 DP
int dp(int idx, int w) {
	if (idx == n)
		return 0;
	if (cache[idx][w] != -1)
		return cache[idx][w];
	if (weight[idx] + w <= k)
		return cache[idx][w] = max(dp(idx + 1, w), dp(idx + 1, w + weight[idx]) + value[idx]);
	else
		return cache[idx][w] = dp(idx + 1, w);
}

int main() {
	fscanf(in, "%d %d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		fscanf(in, "%d %d", &weight[i], &value[i]);
	}
	memset(cache, -1, sizeof(cache));
	printf("%d",dp(0, 0));
	return 0;
}