| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1317907 | pancankes | Knapsack (NOI18_knapsack) | C++17 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <array>
#include <cmath>
using namespace std;
using ll = long long;
const int MAXN = 1e5+1;
const int MAXW = 2e3+1;
void setIO(string name="") {
ios_base::sync_with_stdio(0); cin.tie(0);
}
// naive approach: put k copies of everythign into one vector, run standard 0/1 knapsack
// fails on K <= 1e9,
// W <= 2000. N*W means that naive 0/1 fails anyways.
void solve()
{
int x,n;
cin >> x >> n;
map<int,vector<pair<int,int>>> by_w;
for (int i=1; i<=n; i++) {
int v,w,k;
cin >> v >> w >> k;
by_w[w].push_back({v,k});
}
for (int i=0; i<=n; i++) {
}
vector<vector<ll>> dp(by_w.size() + 1,vector<ll>(x + 1, INT32_MIN)); // initiliase all values of dp vector as INT32_min
dp[0][0]=0;
int at=1;
// grouped the items by weight, sort by decreasing value
// only need to consider the first x/w items
for (auto &[w,items] : by_w) {
sort(items.rbegin(),items.rend());
for (int j=0; j<=x; j++) {
dp[at][j]=dp[at-1][j];
// implementation: go through as many items at weight w
// until we have no space: (copies + 1) * w <= j OR;
// until we have no more copies at weight w
ll copies=0, type=0, cur=0, totalv=0;
while ((copies+1) * w <= j && type < items.size()){
copies++;
totalv+=items[type].first;
if (dp[at-1][j-copies*w] != INT32_MIN) { // here we need a check to see if it's even possible to make dp[i][j];
dp[at][j]=max(dp[at][j],dp[at-1][j-copies*w]+totalv);
}
// need to implement the logic of moving on to the next item
cur++;
if (cur==items[type].second) {
type++;
cur=0;
}
}
}
at++;
}
cout << *max_element(dp.back().begin(),dp.back().end()) << endl;
}
int main()
{
setIO();
solve();
}