Hướng giải của Knapsack vét cạn

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: Quay lui: tại mỗi đồ thử hai nhánh (lấy/không lấy). Cắt tỉa bằng nhánh cận: tính tổng giá trị còn lại remaining, nếu cur_v + remaining <= best thì dừng nhánh này.

Độ phức tạp: \(O(2^n)\) thời gian (nhánh cận giúp chạy nhanh hơn nhiều), \(O(n)\) stack.

C++

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

int n;
long long w[22], v[22], W, best;

void backtrack(int i, long long cur_w, long long cur_v) {
    if (i == n) { best = max(best, cur_v); return; }
    if (cur_w + w[i] <= W)
        backtrack(i + 1, cur_w + w[i], cur_v + v[i]);
    long long remain = 0;
    for (int j = i; j < n; j++) remain += v[j];
    if (cur_v + remain > best)
        backtrack(i + 1, cur_w, cur_v);
}

int main() {
    cin >> n >> W;
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    backtrack(0, 0, 0);
    cout << best << "\n";
    return 0;
}

Python

def backtrack(i, cur_w, cur_v):
    global best
    if i == n:
        best = max(best, cur_v)
        return
    if cur_w + w[i] <= W:
        backtrack(i + 1, cur_w + w[i], cur_v + v[i])
    remain = sum(v[i:])
    if cur_v + remain > best:
        backtrack(i + 1, cur_w, cur_v)

n, W = map(int, input().split())
w, v = [], []
for _ in range(n):
    wi, vi = map(int, input().split())
    w.append(wi); v.append(vi)
best = 0
backtrack(0, 0, 0)
print(best)

Nhận xét

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