Noic - Semana 50 - Nível Avançado

noic-semana50-avanc.cpp

// Noic - Semana 50 - Avançado
// Complexidade: O(N*V)

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 110;
const int maxv = 1e5+10; // maior resposta possível

int w[maxn], v[maxn];
 
int dp[maxn][maxv];
 
int main(void)
{
	int n, W;
	cin >> n >> W;
 
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
 	
 	// Casos Base
	for (int i = 0; i <= n; i++)
	{
		dp[i][0] = 0;
		for (int j = 1; j < maxv; j++)
			dp[i][j] = W+1; // por enquanto, daremos um valor grande
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < maxv; j++)
		{
			// precisamos checar se é possível usar v[i]
			if (j >= v[i]) dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
			else dp[i][j] = dp[i-1][j];
		}
	}
 
	int ans = 0;
	for (int i = 1; i < maxv; i++)
		if (dp[n][i] <= W) ans = i;
 
	cout << ans << "\n";
}