Submission #1129226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129226		jackofall718	Knapsack (NOI18_knapsack)	C++20	100 / 100	96 ms	1776 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Global variables for storing the capacity of the knapsack, number of items, value, weight, and number of copies respectively.
int S, N, V, W, K;

// A is an array of vectors, where each vector holds pairs of value and count for items of a particular weight.
vector <pair<int, int>> A[2001];

// dp array to store the maximum value obtainable with a certain weight, answer variable to keep the maximum result.
long long dp[2001], answer;

int main(){
    // Input the capacity of the knapsack and number of different types of items
    cin >> S >> N;

    // Reading the value, weight, and number of copies of each item
    for(int i = 0; i < N; i++){
        cin >> V >> W >> K;
        // Storing value and the number of copies for each weight
        A[W].push_back(make_pair(V, K));
    }

    // Iterate through each possible weight from 1 up to the maximum weight capacity S
    for(int i = 1; i <= S; i++){
        // If there are items of weight i, sort them by value in descending order (higher value first)
        sort(A[i].begin(), A[i].end(), greater<pair<int, int>>());

        int index = 0; // Index to track the number of different value groups of the current weight

        // Iterate j times where j is the maximum number of items of weight i that can be included without exceeding the capacity
        for(int j = 0; j < S / i; j++){
            // Check if there are no more items left of the current weight
            if(index >= A[i].size()) break;

            // Iterate through the knapsack weights from the capacity down to the current item weight
            for(int k = S; k >= i; k--){
                // Update dp[k] to be the max of itself or the value of including one more of the current item
                dp[k] = max(dp[k], dp[k - i] + A[i][index].first);
                // Update the answer with the maximum value found so far
                answer = max(answer, dp[k]);
            }
            
            // Decrement the number of available copies of the current item
            A[i][index].second--;

            // If all copies of the current item are used, move to the next group of items of the same weight
            if(A[i][index].second == 0) index++;
        }
    }

    // Output the maximum value that can be obtained
    cout << answer << endl;
    return 0;
}

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