Bài toán cái túi 0-1

#1

Chào mọi người, chắc hẳn là không ai xa lạ với bài toán cái túi. Nhưng vấn đề em gặp phải là đề bài cho khối lượng túi rất lớn, và yêu cầu đưa ra giá trị tối đa được chọn và các phần tử được chọn. Em đã biết dùng quay lui + phân tập để tìm giá trị của phần tử nhưng không có cách nào để truy hồi các phần tử được chọn. Nếu ai biết thì mong mọi người cho biết làm bằng cách nào và nếu được thì có thể cho em các bài tập đơn giản/ website để luyện thuật toán đó. Em cảm ơn

1 Like
#2

quy hoạch động là có 1 mảng chứa giá trị tối đa rồi, + thêm 1 mảng from là cho biết f[i][w] từ đâu đến nữa là được mà :V

wiki có đầy đủ mà https://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem

3 Likes
#3

ý mình là khối lượng quá lớn, không thể quy hoạch động mà phải quay lui ấy bạn, mình không biết truy hồi bằng quay lui

Ví dụ
input
nhập vào n đồ vật, bao tải có sức chứa m ( n <= 35,
10^6 <= m <= 10^9)

#4

Do mỗi giá trị chỉ có 2 lựa chọn nên ta dùng số nhị phân 32 bit uint32_t (vì unsigned không bị undefined) để thể hiện lựa chọn đó, tức là bit thứ i sẽ lưu lựa chọn của a[n-i].

3 Likes
#5

mình có hiểu ý bạn 1 chút nhưng vẫn không hình dung được
Giả sử như này đi

Có 4 đồ vật, bao tải chứa tối đa 10kg
Đồ vật thứ: 1 2 3 4
Giá trị của đồ vật: 2 4 4 5
Trọng lượng của vật: 1 3 5 7
Đáp án là chọn các đồ vật thứ 1, 2, 3.

Theo cách làm của mình:
mình sẽ quay lui 2 đồ vật đầu tiên
Thì mình sẽ có một dãy d1 chứa các giá trị các đồ vật : 0; 2; 4; 6 (đồng thời lưu lại trọng lượng của các đồ vật có thể chứa vào bao tải)
Mình quay lui 2 đồ vật còn lại
Mình sẽ có dãy d2: 0; 4; 5; 9
Sau đó mình lấy kết quả bằng cách cộng các phần tử của d1 với các phần tử d2 với điều kiện là có giá trị lớn nhất và trọng lượng <= 10kg

Ý tưởng của mình là vậy nhưng để đưa ra các vị trí đồ vật được chọn thì mình không biết. Làm phiền bạn thêm 1 tí nữa giúp đỡ mình :pray:

#6

Xét dãy d gồm các bộ (w, v, c) với d_c là dãy nhị phân biểu thị cách chọn để d_w < 10
Vậy:

\begin{aligned} d_1 &= [(0,0,00_2),(1,2,10_2),(3,4,01_2),(4,6,11_2)]\\ d_2 &= [(0,0,00_2),(5,4,10_2),(7,5,01_2)] \end{aligned}

Do d_2 ngắn hơn nên sinh ra dãy d = [(4,6,1100_2),(9,10,1110_2),(10,9,0101_2)].
Lấy bộ có v lớn nhất trong d thì ra được cách chọn là 1110_2 hay chọn vật 1, 2 và 3.

2 Likes
#7

n <= 35 thì thay vì xài dp mảng m phần tử đi xài đệ quy memoize có cache là hash map ấy :V :V

// cache[{i, w}] = {total value, from}
std::unordered_map<std::pair<int, int>, std::pair<long, std::pair<int, int>>> cache;

// m[0, w] = 0
// m[i, w] = m[i - 1, w] if W[i] > w
// m[i, w] = max(m[i - 1, w], m[i - 1, w - W[i]) + V[i]) if W[i] <= w
// return value = {total value, from}
std::pair<long, std::pair<int, int>> knapsack01(const std::vector<int>& V, const std::vector<int>& W, int i, int w) {
    const auto key = std::make_pair(i, w);
    if (cache.count(key) > 0) return cache[key];
    // m[0, w]
    if (i == 0) return cache[key] = std::make_pair(0, key); // from == current nghĩa là kết thúc
    // m[i - 1, w]
    const auto [total1, from1] = knapsack01(V, W, i - 1, w);
    if (W[i] > w) return cach[key] = std::make_pair(total1, std::make_pair(i - 1, w));
    // m[i - 1, w - W[i]) + V[i]
    auto [total2, from2] = knapsack01(V, W, i - 1, w - W[i]);
    total2 += V[i];
    if (total1 < total2) return cache[key] = std::make_pair(total2, std::make_pair(i - 1, w - W[i]));
    return cach[key] = std::make_pair(total1, std::make_pair(i - 1, w));
}

đại loại như thế này (V, W bắt đầu từ index 1)

tìm item nào lấy thì cứ backtrack

int w = ...;
int i = n;
std::vector<int> chosenIds;
while (1) {
    const auto [_, from] = knapsack01(V, W, i, w);
    const auto [i1, w1] = from;
    if (i1 == i && w1 == w) break;
    if (w != w1) chosenIds.push_back(i); // khác weight nghĩa là take current item
    i = i1;
    w = w1;
}

ơ ờ do n <= 35 nên có thể rút gọn size cho cái cache bằng cách lưu chosenIds dưới dạng int 64-bit luôn ấy :V :V chứ hiện tại cache nó lưu hết ~ n * w thì hơi nhiều chăng :V :V

à chạy thử https://rextester.com/IJHDVD35118 n=10, w=2e6 thì cache size có 584 à chứ đâu lên tới nw = 20tr đâu

edit: cache size ~ 2^n, vậy n=35 cũng chết :V :V :V test thử n=25 đã chết rồi :V :V đề nó cho đẹp nhỉ, nw = 3.5e10, 2^n cũng ~ 3.5e10

3 Likes
#8

mình cảm ơn bạn nhiều, mình hiểu rồi, chỉ có thắc mắc là số 2 nhỏ nhỏ đó có ý nghĩa gì vậy bạn

#10

Số 2 nhỏ ý chỉ là số nhị phân (cơ số 2).

3 Likes
#11

Cảm ơn hướng dẫn của bạn. Không biết bạn có nhu cầu hay không, nếu bạn muốn nghiên cứu thì đây là đề :slight_smile:

422134561_368503052603720_7662043981312077992_n
422134561_368503052603720_7662043981312077992_n918×1632 85.5 KB

#12

ủa w[i] giới hạn < 1000 vậy n < 40 thì w tối đa có 40k chứ nhiêu mà cho 1e9 :hocho:
lấy tổng weight của n items gọi là m’, set m = min(m, m’) rồi qhđ bình thường O(nm) :hocho: :hocho: :hocho: à tính tổng m’ của n items, nếu m >= m’ thì lấy hết ko cần qhd. Còn lại qhd bình thường tối đa có 1e6 chứ nhiêu

3 Likes
#13

ui tại mình nhớ mang máng rồi đề rồi mới lên hỏi, sorry bạn.
Nhưng mà cảm ơn bạn nhiều

#14

Chào mọi người, hôm nay em làm lại đề này vì bây giờ mới kiếm được bộ chấm của nó (trước kia làm xong thấy đúng test mẫu nên khăng khăng là đúng rồi). Lúc em kiểm tra thì nó đúng hết trừ subtask 2, mặc dù em đã chia đôi tập này nọ rồi, nhưng vẫn quá thời gian. Ai biết giúp em với, em cảm ơn!
Code phần subtask 1 & 2 của em:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<unordered_map>
#define all(a) a.begin(), a.end()
#define fr(i, zz, zzz) for (int i = zz; i <= zzz; i++)
#define frr(i, zz, zzz) for (int i = zz; i >= zzz; i--)
#define full(asdf) memset(asdf, 0, sizeof(asdf))
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define IOS ios_base::sync_with_stdio(0);   cin.tie(0); cout.tie(0);
#define condition x >= 1 && x <= n & y >= 1 && y <= n
using namespace std;
const int N = 1E3 + 5;

struct arr {
    int st, nd;
    string rd;
};

int n, m;
int dp[N][N];
pii a[N];
vector<arr> b, c;
vector<string> str;
vector<int> ans;
 
bool cmp(arr a, arr b) {
    return (a.st < b.st) || (a.st == b.st && a.nd > b.nd);
}
 
 void input() {
    cin >> n >> m;
    fr(i, 1, n)
        cin >> a[i].st >> a[i].nd;
 }
 
 void Try(int i, int length, string s, int val, int wei, vector<arr> &d) {
    if (i > length) {
        if (wei <= m) {
            d.push_back({wei, val, s}); 
        }
        return;
    }
    Try(i + 1, length, s + "1", val + a[i].nd, wei + a[i].st, d);
    Try(i + 1, length, s + "0", val, wei, d);
 }
 
 void Case_1() {
    int mx = 0, j = 0, res = 0, cnt = 0;
    string str = "", ress = "";
    Try(1, n/2, "", 0, 0, b);
    Try(n/2 + 1, n, "", 0, 0, c);
    sort(all(b), cmp);
    sort(all(c), cmp);
    frr(i, b.size() - 1, 0) {
            while (j < c.size() && b[i].st + c[j].st <= m) {
                if (mx < c[j].nd) {
                    mx = c[j].nd;
                    str = c[j].rd;
                }
                ++j;
            }
            if (res < mx + b[i].nd) {
                res = mx + b[i].nd;
                ress = b[i].rd + str;
            }
        }   
    cout << res << "\n";
    fr(i, 0, ress.size() - 1)
        if (ress[i] == '1')
            cout << i + 1 << " ";  
 
 }
int main() {
    input();
    Case_1();
}
#15

Bạn đăng đầy đủ code có define lên đây nhé.

1 Like
#16

rồi ạ, nhờ anh kiểm tra giúp!

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?