https://www.acmicpc.net/problem/12865
DP를 이용하여 Top-down 방식으로 해결해보았다.
f(i, kg)는 i번째 물건을 넣을지 말지 판별 시에, 현재 배낭에 kg만큼 무게가 차있을 때의 최대 가치값을 리턴하는 함수이다.
처음에는 최초 함수 호출을 f(0, 0) 호출 대신 f(N-1,K) 호출로 생각하여 Base 조건을 찾는게 까다롭게 느껴졌으나,
f(0, 0)로 첫 함수 호출을 하여 i가 N 이상일 때, kg가 K 초과 시 0을 리턴하며 함수 호출이 끝나도록 조건을 거꾸로 생각하니 처음보다 수월하게 구현되었다.
아직 dp배열을 유지하는 레퍼런스 타입 변수 ret의 사용이 익숙치 않아서 DP 문제를 해결하며 숙련도를 높여야 한다.
#include<iostream>
#include<string.h>
using namespace std;
int w[101], v[101];
int dp[101][100001];
int N, K;
int f(int i, int kg) {
if (i >= N || kg > K) return 0;
int& ret = dp[i][kg];
if (ret != -1) return ret;
if (K - kg >= w[i]) {
ret = max(f(i + 1, kg), f(i + 1, kg + w[i]) + v[i]);
}
else {
ret = f(i + 1, kg);
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> K;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < N; i++) {
int iptW, iptV;
cin >> iptW >> iptV;
w[i] = iptW;
v[i] = iptV;
}
cout << f(0, 0);
return 0;
}