백준 12865번: 평범한 배낭

[문제 링크]

12865번: 평범한 배낭

---

간단한 다이나믹 프로그래밍 문제였다.

입력받은 물품 목록 배열에서, 현재 보고있는 물품의 무게가 준서가 버틸 수 있는 무게보다 무겁지 않을 경우 해당 물품을 가방에 담았을 때 나올 수 있는 최대 가치값과 담지 않았을 때 나올 수 있는 최대 가치값을 비교하여 더 큰 가치값을 선택하도록 구현하면 된다.

 

따라서 점화식은 다음과 같다.

maxValue = max(dp(here+1, weight + itemWeight) + itemValue , dp(here+1, weight))

---

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int N, K, V, W;
int memo[101][100001];

//first : W, second : V
vector<pair<int, int>> item;

int dp(int here, int weight) {
	// 기저사례 : N개의 물건을 모두 탐색했다면 재귀를 종료한다.
	if (here == N) return 0;

	int& ret = memo[here][weight];
	if (ret != -1) return ret;

	if (weight + item[here].first <= K)
		return ret = max(dp(here + 1, weight + item[here].first) + item[here].second, dp(here + 1, weight));
	else
		return ret = dp(here + 1, weight);
}

int main(void) {
	memset(memo, -1, sizeof(memo));

	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> W >> V;
		item.push_back({ W,V });
	}

	cout << dp(0, 0) << endl;
}