[BOJ] 평범한 배낭

[BOJ] 평범한 배낭

Problem URL : 평범한 배낭

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

using namespace std;

int N, K;
vector<pair<int, int>> item;
int dp[100][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 j = 0; j <= K; j++) {
		if (item[0].first <= j) dp[0][j] = item[0].second;
	}

	for (int i = 1; i < N; i++) { //item 번호
		for (int j = 0; j <= K; j++) { //j: 무게(W)
			if (item[i].first <= j) {
				/* j만큼의 무게를 활용하는데 있어서 최선의 결과는 
				   i번째 item을 포함할때, 안할 때 두 경우 중 최댓값*/ 
				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";
}