Submission #669833

#	Time	Username	Problem	Language	Result	Execution time	Memory
669833		rv4102	Knapsack (NOI18_knapsack)	C++17	100 / 100	127 ms	3708 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int capacity, n;
    cin >> capacity >> n;
    // vector<int> price(n), weight(n), copies(n);
    // for(int i=0; i<n; i++){
    //     cin >> price[i] >> weight[i] >> copies[i];
    // }

    // vector<int> dp(capacity+1, 0);
    // for(int i=0; i<n; i++){
    //     int max_copies = capacity / weight[i];
    //     for(int j=1; j<=min(max_copies, copies[i]); j++){
    //         for(int wt=capacity; wt>=0; wt--){
    //             if(wt >= weight[i])
    //                 dp[wt] = max(dp[wt], dp[wt-weight[i]] + price[i]);
    //             else
    //                 break;
    //         }
    //     }
    // }

    // cout << dp[capacity] << endl;

    vector<vector<pair<int, int>>> item_grp_by_wt(capacity+1);
    for(int i=0; i<n; i++){
        int price, weight, copies;
        cin >> price >> weight >> copies;
        item_grp_by_wt[weight].push_back({price, copies});
    }

    // evaluate by taking each item group and sorting it on the basis of their prices. 
    vector<int> dp(capacity+1, 0);
    for(int i=1; i<=capacity; i++){
        // descending order sort
        sort(item_grp_by_wt[i].rbegin(), item_grp_by_wt[i].rend());
        int item_cnt = 0;

        // for each item in the weight group
        for(auto& p: item_grp_by_wt[i]){
            int price = p.first;
            int copies = p.second;
            for(int j=1; j<=copies; j++){
                // we evaluate each copy of a particular item here
                // if the count exceeds capacity then go to another item class
                if(item_cnt * i > capacity)
                    break;
                
                // update dp array
                for(int wt = capacity; wt>=i; wt--){
                    dp[wt] = max(dp[wt], dp[wt-i] + price);
                }
                item_cnt++;
            }
        }
    }

    cout << dp[capacity] << endl;
}

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