Submission #502105

#	Time	Username	Problem	Language	Result	Execution time	Memory
502105		ditsipandey	Knapsack (NOI18_knapsack)	C++14	100 / 100	88 ms	34416 KiB

knapsack

// https://oj.uz/problem/view/NOI18_knapsack
/* in a knapsack problem the decision making is basically dependent on the min or max statement */
#include<bits/stdc++.h>
using namespace std;



#define ite(i,n) for(int i=0;i<n;i++)
#define itel(i,n) for(ll i=0;i<n;i++)
#define fora(i,a,b) for(int i=a;i<b;i++)
#define fors(i,a,b) for(int i=a;i>=b;i--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef std::set<ll>::iterator set_p ;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define reached cout<<"reached"<<endl
ll MOD=1e9+7;

/*--------------------------------------Printing functions start----------------------------------------------*/
template<typename T>
void print_vec(vector<T>&vec){
    for(auto i=vec.begin();i!=vec.end();i++){
        cout<<*i<<" ";
    }
    cout<<"\n";
}

template<typename T>
void print_2Dvec(vector<vector<T>>&vec){
    for(int i=0;i<vec.size();i++){
        for(int j=0;j<vec[i].size()>0;j++){
            cout<<vec[i][j]<<"\t";
        }
        if(vec[i].size()>0)
            cout<<"\n";
    }
}
template<typename T, typename S>
void print_pair(pair<T,S> a){
    cout<<a.first<<" "<<a.second<<"\n";
}

/*---------------------------------------Printing functions end-----------------------------------------------*/
/*---------------------------------------Graph functions------------------------------------------------------*/
// vector<int>dist(1e5+1,INT_MAX);
// vector<int>par(1e5+1, INT_MAX);
// vector<bool>visited(100001,0);
// vector<vector<int>>graph(2*(1e5)+1);

// template<typename T>
// void g_input(T n,T m){
//     for(T i=0;i<m;i++){
//         int a,b;
//         cin>>a>>b;
//         graph[a].push_back(b);
//         graph[b].push_back(a);
//     }
// }

// void bfs(int s){
//     dist[s]=1;
//     queue<int>q;
//     q.push(s);
//     while(!q.empty()){
//         int t=q.front();
//         q.pop();
//         for(int i=0;i<graph[t].size();i++){
//             if(dist[graph[t][i]]==INT_MAX){
//                 dist[graph[t][i]]=dist[t]+1;
//                 par[graph[t][i]]=t;
//                 q.push(graph[t][i]);
//             }
//         }
//     }

// }

// void dfs(int n){
//     visited[n]=1;
//     // cout<<n<<"\n";
//     for(int i=0;i<graph[n].size();i++){
//         if(!visited[graph[n][i]]){
//             dfs(graph[n][i]);
//         }
//     }
// }

/*---------------------------------------Graph functions------------------------------------------------------*/

// int main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     int s,n;
//     cin>>s>>n;
//     if(n==1){
//         int v,w,k;
//         cin>>v>>w>>k;
//         int ans= min((s/w),k)*v;
//         cout<<ans<<endl;
//         return 0;
//     }
//     int v,w,k;
//     vector<pii>list;
//     list.push_back({0,0});
//     ite(i,n){
//         cin>>v>>w>>k;
//         for(;k>0;k--){
//             list.push_back({w,v});
//         }
//     }
//     sort(list.begin(), list.end());
//     n=list.size()-1;
//     vector<vi>dp(2,vi(s+1,0));
//     for(int i=1;i<n+1;i++){
//         int x=i%2;
//         for(int j=1;j<s+1;j++){
//             if(j>=list[i].first) dp[x][j]=max(dp[x^1][j-list[i].first]+list[i].second, dp[x^1][j]);
//         }
//     }
//     // print_2Dvec(dp);
//     cout<<dp[n%2][s]<<endl;
//     return 0;
// }
 int main(){
     fast;
     map<ll,vector<pll>>m;
     ll n,s;
     cin>>s>>n;
    itel(i,n){
        ll v,w,k;
        cin>>v>>w>>k;
        m[w].push_back({v,k});
    }
    vector<vll>dp(m.size()+1, vll (s+1,INT32_MIN)); //int32_min chosen to show the not possible case
    dp[0][0]=0; // attaining 0 with a 0 weighted item is possible with maximum achieveble value to be 0
    ll a=1;
    for(auto& p : m){
        ll w=p.first;
        sort(p.second.begin(), p.second.end(), greater<pll>());
        vector<pll> items = p.second;
        for(int j=0;j<s+1;j++){
            dp[a][j]=dp[a-1][j]; //considers the possibility of not choosing any items of the weight category w
            // #important analyse it definitely
            ll copies=0;   // copies keeps track of many values of weight w have i used until now. It will not be updated to 0 after k_count reaches items[type].second 
            ll type=0; // basically keeps track of the type i am currentyl at in the items list. Type will be incremented when k_count reaches items[type].second
            ll k_count=0;  // keeps track if i reached k after eaach iteration. REset to 0 when it reaches items[type].second. Has to be incremented b4 the check 
            ll profit=0; //counts the total value being added at each weight type whilecomparing for the max imum value of dp[a][j]
            /* what to do now:  I need to maximise the value of each dp[a][j]. I can either choose some of the first category of items or the second as the items
               are arranged in reverse order of value i can simply choose all of the first category of items before moving on to the second one.  */
            while((copies+1)*w<=j && type<items.size()){
                copies++;
                profit+=items[type].first;
                if(dp[a-1][j-copies*w]!=INT32_MIN){
                    // dp[a][j]=max(dp[a-1][j-copies*w]+items[type].first,dp[a][j]); // Why will this line code not give the correct answer:  Because while we are checking the addition of items[type].first we are not actually checking when the this particular value is being repeated again and again
                    dp[a][j]=max(dp[a-1][j-copies*w]+profit,dp[a][j]); //here it is dp[a][j] and not dp[a-1][j] because then consecutive comparisons to decide the best choice for which copies is present would also not be possible
                }
                k_count++;
                if(k_count == items[type].second){
                    k_count=0;
                    type++;
                }
            }
            
        }
        a++;
    }
    // print_2Dvec(dp);
    cout<<*(max_element(dp.back().begin(),dp.back().end()))<<endl; //this dp checks the attainability of a particular sum against the value as well so the notion of considering all possibilites is used by taking max_element
 }

 

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:153:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             while((copies+1)*w<=j && type<items.size()){
      |                                      ~~~~^~~~~~~~~~~~~

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