Submission #1194024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194024		dungtt	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	324 KiB

knapsack

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

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

    int N;             // Số loại vật liệu
    ll W;              // Sức chứa của balo (trọng lượng tối đa)
    cin >> N >> W;

    // Mảng dp[j] lưu giá trị tối đa khi cân nặng chính xác là j
    vector<ll> dp(W+1, 0);

    // Duyệt qua từng loại vật liệu
    for(int i = 0; i < N; i++) {
        ll w, v, k;
        cin >> k >> w >> v; // Đọc số lượng k, trọng số w, giá trị v của loại vật i

        // Nếu một vật chiếm trọng lượng 0 và có giá trị dương, ta có thể lặp vô hạn.
        // Tuy nhiên, nếu w = 0 nhưng v <= 0 hoặc dp không đổi, ta bỏ qua luôn.
        if (w == 0) continue;

        // Nếu K rất lớn: đủ để lấp đầy mọi trọng số, coi như knapsack không giới hạn
        if (k * w >= W) {
            // Cập nhật như bài toán unbounded knapsack (lấy không giới hạn)
            // Duyệt từ trọng lượng w đến W (tăng dần) để không dùng một vật nhiều lần trong cùng một lần lặp
            for (ll j = w; j <= W; j++) {
                dp[j] = max(dp[j], dp[j - w] + v);
            }
            continue;
        }

        // Trường hợp bounded knapsack với k nhỏ: dùng sliding window
        // Tạo bản sao dp cũ để tham chiếu (những giá trị trước khi thêm loại vật này)
        vector<ll> dp_old = dp; 

        // Duyệt các phần dư r = 0..w-1
        for(int r = 0; r < w; r++) {
            // Sử dụng deque để lưu các cặp (t_index, H_value)
            deque<pair<ll,ll>> dq;
            // t là số đơn vị w đang xét, tương ứng vị trí j = r + t*w
            ll max_t = (W - r) / w;
            for(ll t = 0; t <= max_t; t++) {
                ll j = r + t * w;
                ll H = dp_old[j] - t * v; // giá trị H(t) = dp_old[r+t*w] - t*v

                // Loại bỏ chỉ số đã ra khỏi phạm vi cửa sổ (t - k)
                while (!dq.empty() && dq.front().first < t - k) {
                    dq.pop_front();
                }
                // Đưa chỉ số mới t vào deque, giữ thứ tự H giảm dần
                while (!dq.empty() && dq.back().second <= H) {
                    dq.pop_back();
                }
                dq.emplace_back(t, H);

                // Cập nhật dp[r + t*w] = dp_new[r+t*w]
                // Công thức: t*v + max(H(u) trong cửa sổ) = deque.front().second + t*v
                ll best = dq.front().second + t * v;
                dp[j] = max(dp[j], best);
            }
        }
    }

    // Kết quả: giá trị lớn nhất trong dp[0..W]
    ll ans = 0;
    for(ll j = 0; j <= W; j++) {
        ans = max(ans, dp[j]);
    }
    cout << ans;
    return 0;
}

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