I have been trying to fix the bug in my code for this problem: https://oj.uz/problem/view/NOI18_knapsack. Any help would be very much appreciated.
Spoiler
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2002;
vector<pair<ll, ll>> a[MAX];
ll f[MAX][MAX], s, n, u, v, w, k, total;
void solve() {
cin >> s >> n;
for (int i = 1; i <= n; i++) {
cin >> v >> w >> k;
a[w].push_back({v, k});
}
for (int i = 1; i <= 2000; i++) sort(a[i].begin(), a[i].end(), greater<pair<ll, ll>>());
for (int i = 1; i <= s; i++) {
for (int j = 1; j <= s; j++) {
total = 0;
ll temp = 0;
f[i][j] = f[i - 1][j];
for (auto u : a[i]) {
if (total + u.second * i <= j) {
total += u.second * i;
temp += u.second * u.first;
f[i][j] = max(f[i][j], temp + f[i - 1][j - total]);
} else {
temp += (j - total) / i * u.first;
total += (j - total) / i * i;
f[i][j] = max(f[i][j], temp + f[i - 1][j - total]);
break;
}
}
f[i][j] = max(f[i][j], temp + f[i - 1][j - total]);
//if (i > 19) cout << f[i][j] << " ";
}
//if (i > 19) cout << "\n";
}
cout << f[s][s];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
Auto comment: topic has been updated by mustard_with_fries69420 (previous revision, new revision, compare).
Sorry about the bad format of the code, I don't know how to make it better.oh, thanks!
Can someone help please?
I had a hard time understanding the way your code worked. But I think the problem is in the algorithm. If I understand your code correctly, you're trying to maximize the number of items you pick in each type of thing. But I think the lemma isn't true (Maybe there exists a proof or a counter-example(??), but I didn't try to find it). For the correct algorithm to solve the problem, this is my attempt: We call dp[i][j] as the maximum value we can achieve by choosing only the items with a weight smaller or equal to i, and the total weight is j. It's easy to see that dp[i][j] = max(dp[i-1][j-k*i] + val) (j-k*i >= 0) with val as the maximum value you can achieve by choosing k items with the weight of i (this can be easily calculated in O(1) using a simple greedy strategy). For the running time analysis, we see that to calculate dp[i][j], we have to loop through approximately i/j values of k. Summing with all i and j from 1 to n we have the number of operations required is (1+2+3+4+...+S)*(1/1+1/2+1/3+...+1/S). The first term is O(S^2), and the second term is just the harmonic series (it can be easily proved that O(1/1+1/2+1/3+...+1/S) = O(log S), but the proof is left as an exercise). So the total complexity is O(S^2 log S) with a pretty small constant, I think. Hope this help. P/s: sorry for bad quality comment and bad English skill