Pagini recente » Cod sursa (job #538638) | Cod sursa (job #910152) | Cod sursa (job #2028324) | Cod sursa (job #740764) | Cod sursa (job #3248495)
// PULL-DP KNAPSACK optimised
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//#define fin cin
//#define fout cout
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int MAX_WEIGHT = 10000, MAX_OBJECTS = 5000;
int n,w;
pair<int,int> objects[MAX_OBJECTS + 1];
// dp[weight][numberOfObjects]
int dp[MAX_WEIGHT + 1];
int ans = 0;
int main() {
fin >> n >> w;
for (int i = 1; i <= n; i++) {
int a,b;
fin >> a >> b;
objects[i] = {a,b};
}
dp[0] = true;
for (int it = 1; it <= n; it++) {
const pair<int,int>& object = objects[it];
for (int weight = w; weight >= 0; weight--) {
if (dp[weight] and weight + object.first <= w) {
dp[weight + object.first] = max(dp[weight + object.first], dp[weight] + object.second);
ans = max(ans, dp[weight + object.first]);
}
}
}
fout << ans - 1;
return 0;
}