백준 12865 평범한베낭 c++ // 재귀dp, 불가능한경우를 먼저 ret하라

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

 

1. 불가능한경우를 먼저 ret하라

int dfs(int idx, int weight) {
	//기저사례
	//!조건불만족하면 리턴! 이 return이 먼저와야함!! -> 그래야 배제가능.
	// 안그러면, 조건불만족 인데 idx==n인 경우도 유효한 경우로 카운팅됨.
	if (weight > k) { 
		return -987654321;
	}
	if (idx == n) {
		return 0;
	}

idx==n return 0이 먼저오는 경우 : 조건불만족인데 n에 도달한경우도 유효한 경로로 카운팅이 되어버린다..

 

2. 의사코드

0 번베낭을 담는다, 안담는다

1번 베낭을 담는다 안담는다 ... 로 완탐하고

dp[idx][weight] 의 상태를 배열에 저장해놓는다.

 

3. 전체코드

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, k,dp[104][100000+4],w[104],v[104];

int dfs(int idx, int weight) {
	//기저사례
	//!조건불만족하면 리턴! 이 return이 먼저와야함!! -> 그래야 배제가능.
	// 안그러면, 조건불만족 인데 idx==n인 경우도 유효한 경우로 카운팅됨.
	if (weight > k) { 
		return -987654321;
	}
	if (idx == n) {
		return 0;
	}
	
	if (dp[idx][weight] != -1) return dp[idx][weight];

	dp[idx][weight] = 0;
	//이번베낭을 안담는경우, 담는경우
	dp[idx][weight] = max(dfs(idx+1,weight),dfs(idx+1,weight+w[idx])+v[idx]);

	return dp[idx][weight];
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	memset(dp, -1, sizeof(dp));
	cin >> n>>k;
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a>>b;
		w[i] = a;
		v[i] = b;
	}

	//0번 가방을 담는경우, 안담는경우로 시작
	cout << dfs(0, 0);
	return 0;
}