Submission #1156895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156895		mohsina	Knapsack (NOI18_knapsack)	C++20	37 / 100	4 ms	1096 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int main()
{
//     The first line of input contains two positive integers, S and N.
// The next N lines of input will each contain three integers, where the i-th line contains Vi
// , Wi
// and Ki
// , the value in SGD, weight in kilograms and number of the i-th item respectively
//For all subtasks, 1 ≤ S ≤ 2000bagWeight, 1 ≤ Vi ≤ 1000000, 1 ≤ Wi ≤ S.
    int bagWeight=0,items=0;
    cin>>bagWeight>>items;
    vector<int> values(items,0),weights(items,0),counts(items,0);
    for(int i=0;i<items;i++){
        cin>>values[i]>>weights[i]>>counts[i];
    }
    // vector<vector<int>> dp(items,vector<int> (bagWeight+1,-1));
    // for(int i=0;i<items;i++){
    //     dp[i][0]=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
        int currWeight=0;
        int currValue=0;
        for(int k=counts[i];k>=0;k--){
            currWeight=k*weights[i];
            currValue=k*values[i];
            // cout<<k<<" curr{w,v} "<<currWeight<<" "<<currValue<<"\n";
            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<<"at i "<<i<<"\n";
    //      for(int i=0;i<=bagWeight;i++){
    //              cout<<dp[i]<<" ";
    //      }
    //      cout<<"\n";
      
    }
    // 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;
}

• Subtask 1: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27