(c++)백준 12865번: 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

[풀이]

DP로 풀 수 있는 0-1 Knapsack문제였다.

DP[i]: 용량이 i만큼 남았을 때 배낭에 넣을 수 있는 아이템 가치의 최댓값

점화식

if W[i] < K : DP[j] = max(DP[j], DP[j-W[i]]+V[i]) 지금까지의 용량 j일 때의 최댓값과 i번째 아이템을 추가 했을 때의 값을 비교

 

#include <iostream>
#include <algorithm>//max
using namespace std;

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

void solution() {
	for (int i = 1; i <= N; i++) {
		for (int j = K; j >= 1; j--) {
			if (W[i] <= j) {
				DP[j] = max(DP[j], DP[j - W[i]] + V[i]);
			}
		}
	}
	cout << DP[K] << '\n';
}

int main() {
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
	}
	solution();
	return 0;
}