Cod sursa(job #2444426)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 31 iulie 2019 15:37:09
Problema Problema rucsacului Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
//ALEXANDRU MICLEA

#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

#include <fstream>
ifstream cin("rucsac.in"); ofstream cout("rucsac.out");

int g[5010];
int v[5010];

int dp[10010];

int main() {

	int N, G;
	cin >> N >> G;

	for (int i = 1; i <= N; i++) {
		cin >> g[i] >> v[i];
		for (int j = G - g[i]; j >= 0; j--) {
			dp[j + g[i]] = max(dp[j + g[i]], dp[j] + v[i]);
		}
	}

	cout << dp[G];

	return 0;
}