Submission #1194021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194021		dungtt	Knapsack (NOI18_knapsack)	C++20	37 / 100	1 ms	328 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int S, N;
    cin >> S >> N; // Đọc trọng lượng tối đa và số loại vật
    vector<int> dp(S + 1, 0); // Khởi tạo mảng DP, dp[j] = giá trị tối đa với trọng lượng j

    // Xử lý từng loại vật
    for (int i = 0; i < N; i++) {
        int V, W, K;
        cin >> V >> W >> K; // Đọc giá trị, khối lượng, số lượng của loại vật thứ i
        
        // Phân tích nhị phân cho loại vật này
        int count = 1;
        while (K > 0) {
            int num = min(count, K); // số lượng trong nhóm hiện tại (1, 2, 4, ..., hoặc phần còn lại)
            int groupValue = num * V;    // giá trị của nhóm vật này
            int groupWeight = num * W;   // khối lượng của nhóm vật này
            
            // Cập nhật DP như 0/1 knapsack với vật có giá trị groupValue và khối lượng groupWeight
            for (int j = S; j >= groupWeight; j--) {
                dp[j] = max(dp[j], dp[j - groupWeight] + groupValue);
            }
            
            K -= num;      // Giảm bớt số lượng đã gộp vào nhóm
            count <<= 1;   // Nhân đôi count cho nhóm tiếp theo (1 -> 2 -> 4 -> ...)
        }
    }

    // Kết quả là giá trị tối đa với trọng lượng không vượt quá S
    cout << dp[S] << "\n";
    return 0;
}

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