0/1 배낭 문제 (Knapsack Problem)

#include <iostream>
#include <algorithm>
using namespace std;
int n, w;
int dp[200][200000];
int W[200];
int V[200];
void weight_value_input()
{
	for(int i=1; i<=n; i++){
		cin >> W[i] >> V[i];
	}
}
void input()
{
	cin >> n >> w;
	
	weight_value_input();
}
void knapsack()
{
	for(int i=1; i<=n; i++){
		for(int j=1; j<=w; j++){
			if(j >= W[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]] + V[i]);
			else dp[i][j] = dp[i-1][j];
		}
	}
	
	cout << dp[n][w];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	input();
	knapsack();
	
	return 0;
}