# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
601407 | codergirl | Knapsack (NOI18_knapsack) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int c[maxn],value[maxn],num[maxn], dp[maxn];
int V;
void ZeroOnePack (int cost,int val){
for(int i=V;i>=cost;i--) {
dp[i]=max(dp[i],dp[i-cost] + val);
}
return ;
}
int main() {
int n;
cin>>V>>n; // knapsack size V, n kinds of items
for(int i=1;j<=n;j++) {
cin>>value[i]>>c[i]>>num[i]; // weight, value, quantity
}
for(int i=1;i<=n;i++) {
int k=1;
while(k<num[i]){
ZeroOnePack(k * c[i], k * value[i]);
num[i]-=k;
k*=2;
}
ZeroOnePack(num[i]*c[i],num[i]*value[i]);
}
cout<<dp[V]<<'\n';
}