Hướng giải của Cái túi - Meet in the Middle

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Ý tưởng

Chia đồ vật thành hai nửa, với mỗi nửa sinh toàn bộ các phương án (trọng lượng, giá trị). Với nửa phải, sắp xếp theo trọng lượng và tiền xử lý để với mỗi trọng lượng ta lưu giá trị lớn nhất có thể đạt được với trọng lượng ≤ trọng lượng hiện tại. Duyệt từng phương án của nửa trái, tìm phương án tốt nhất ở nửa phải có tổng trọng lượng ≤ W - w.

Độ phức tạp: O(2^{N/2} × N) thời gian, O(2^{N/2}) bộ nhớ.

C++

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

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

    int n;
    long long W;
    cin >> n >> W;
    vector<pair<long long, long long>> items(n);
    for (auto &p : items) cin >> p.first >> p.second;

    int n1 = n / 2, n2 = n - n1;
    vector<pair<long long, long long>> left(items.begin(), items.begin() + n1);
    vector<pair<long long, long long>> right(items.begin() + n1, items.end());

    vector<pair<long long, long long>> genL, genR;
    for (int mask = 0; mask < (1 << n1); ++mask) {
        long long w = 0, v = 0;
        for (int i = 0; i < n1; ++i)
            if (mask >> i & 1) {
                w += left[i].first;
                v += left[i].second;
            }
        if (w <= W) genL.emplace_back(w, v);
    }
    for (int mask = 0; mask < (1 << n2); ++mask) {
        long long w = 0, v = 0;
        for (int i = 0; i < n2; ++i)
            if (mask >> i & 1) {
                w += right[i].first;
                v += right[i].second;
            }
        if (w <= W) genR.emplace_back(w, v);
    }
    sort(genR.begin(), genR.end());

    vector<pair<long long, long long>> best;
    long long max_v = 0;
    for (auto [w, v] : genR) {
        max_v = max(max_v, v);
        best.emplace_back(w, max_v);
    }

    vector<long long> wR;
    for (auto [w, v] : best) wR.push_back(w);

    long long ans = 0;
    for (auto [w, v] : genL) {
        long long remain = W - w;
        int idx = upper_bound(wR.begin(), wR.end(), remain) - wR.begin() - 1;
        if (idx >= 0)
            ans = max(ans, v + best[idx].second);
        else
            ans = max(ans, v);
    }
    cout << ans << '\n';
    return 0;
}

Python

python
from bisect import bisect_right

def solve(n, W, items):
    n1, n2 = n // 2, n - n // 2
    left, right = items[:n1], items[n1:]

    genL = []
    for mask in range(1 << n1):
        w = v = 0
        for i in range(n1):
            if mask >> i & 1:
                w += left[i][0]
                v += left[i][1]
        if w <= W:
            genL.append((w, v))

    genR = []
    for mask in range(1 << n2):
        w = v = 0
        for i in range(n2):
            if mask >> i & 1:
                w += right[i][0]
                v += right[i][1]
        if w <= W:
            genR.append((w, v))
    genR.sort()

    best = []
    max_v = 0
    for w, v in genR:
        max_v = max(max_v, v)
        best.append((w, max_v))

    weights = [w for w, v in best]
    ans = 0
    for w, v in genL:
        remain = W - w
        idx = bisect_right(weights, remain) - 1
        if idx >= 0:
            ans = max(ans, v + best[idx][1])
        else:
            ans = max(ans, v)
    return ans

n, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
print(solve(n, W, items))

Nhận xét

Không có ý kiến tại thời điểm này.