#include <bits/stdc++.h>
using namespace std;
int main()
{
int bagWeight=0,items=0;
cin>>bagWeight>>items;
vector<int> values(items,0),weights(items,0),counts(items,0);
vector<vector<int>> dp(items,vector<int>(bagWeight+1,0));
dp[0][0]=0;
for(int i=0;i<items;i++){
//picking 0 to k items
cin>>values[i]>>weights[i]>>counts[i];
int currWeight=0;
int currValue=0;
for(int k=counts[i];k>=0;k--){
currWeight=k*weights[i];
currValue=k*values[i];
for(int j=bagWeight;j>=currWeight;j--){
if(i>0){
dp[i][j]=max(dp[i][j],currValue+dp[i-1][j-currWeight]);
}else{
dp[i][j]=max(dp[i][j],currValue);
}
}
}
}
// cout<<"done\n";
// for(int i=0;i<=bagWeight;i++){
// cout<<dp[i]<<" ";
// }
// cout<<"\n";
cout<<dp[items-1][bagWeight]<<"\n";
// vector<int> dp(bagWeight+1,0);
//for a given bagWeight,what is maximum value we can get
// for(int i=0;i<items;i++){
// for(int j=bagWeight;j>=0;j++){
// }
// }
// 15 5
// 4 12 1
// 2 1 1
// 10 4 1
// 1 1 1
// 2 2 1
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |