Submission #1192497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192497		dprto	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	1352 KiB

knapsack

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

int main() {
    int S, N;
    cin >> S >> N;

    vector<int> value(N), weight(N), quantity(N);
    
    // Nhập thông tin các đồ vật
    for (int i = 0; i < N; i++) {
        cin >> value[i] >> weight[i] >> quantity[i];
    }

    vector<long long> dp(S + 1, 0); // dp[i] sẽ lưu giá trị lớn nhất có thể đạt được với trọng lượng i

    for (int i = 0; i < N; i++) {
        // Dùng cách "knapsack 0/1" mở rộng để xử lý số lượng đồ vật có thể chọn.
        for (int j = S; j >= weight[i]; j--) {
            for (int k = 1; k <= quantity[i] && k * weight[i] <= j; k++) {
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }

    cout << dp[S] << endl;

    return 0;
}

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