BOJ - 12865번 평범한 배낭

문제 출처 : https://www.acmicpc.net/problem/12865

문제 난이도

Gold 5

문제 접근법

냅색 알고리즘으로 유명한 문제.
DP를 이용해서 풀 수도 있고, dfs 메모제이션을 이용해서 풀어도 된다.
공통적으로,
1) 짐을 넣는 경우
2) 안 넣고 스킵하는 경우
로 나뉘어서 생각하면 편하다.

통과 코드

dfs 메모제이션

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> item;
int dp[100001][101];
int N, K;

int knapsack(int nowW, int idx) {
	if (idx == N) return 0;
	int nextW = item[idx].first;
	int nextCost = item[idx].second;
	if (dp[nowW][idx]) return dp[nowW][idx];
	int ans = 0;
	if (nextW + nowW <= K) {
		ans = knapsack(nextW + nowW, idx + 1) + nextCost;
	}
	ans = max(ans, knapsack(nowW, idx + 1));
	return dp[nowW][idx] = ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int w, cost;
		cin >> w >> cost;
		item.push_back({ w,cost });
	}
	cout << knapsack(0, 0) << "\n";
	return 0;
}

dp : 냅색 알고리즘

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

/* 평범한 배낭
TYPE: Dynamic Programming

큰 문제를 작은 문제로 나뉘어 푸는 기법, 작은 문제가 반복되는 지 확인한다.
*/

int N, K;
vector<pair<int, int>> item;
int dp[101][100001];


int main() {
	cin >> N >> K;
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < N; i++) {
		int W, V;
		cin >> W >> V;
		item.push_back({ W,V });
	}
	for (int i = 0; i < N; i++) { //i:index
		for (int j = 0; j <= K; j++) { //j:weight
			if (i == 0) {
				if (item[i].first <= j) dp[i][j] = item[i].second;
				continue;
			}
			if (item[i].first <= j) dp[i][j] = max(dp[i - 1][j], item[i].second + dp[i - 1][j - item[i].first]);
			else dp[i][j] = dp[i - 1][j];
		}
	}
	
	cout << dp[N-1][K] <<"\n";
}