Khóa học CTDL và GT

Bài 27.3. Bài toán cái túi có giới hạn (Bounded Knapsack)

Chào mừng bạn quay trở lại với series khám phá Cấu trúc dữ liệu và Giải thuật cùng FullhouseDev! Sau khi tìm hiểu về bài toán Cái túi 0/1 (0/1 Knapsack) kinh điển, hôm nay chúng ta sẽ nâng cấp độ khó một chút với một biến thể thực tế hơn: Bài toán cái túi có giới hạn (Bounded Knapsack Problem).

Bài toán đặt ra là gì?

Nhắc lại về bài toán Cái túi 0/1: bạn có một chiếc túi với sức chứa cố định, và một tập hợp các vật phẩm, mỗi vật phẩm có cân nặng và giá trị. Với mỗi vật phẩm, bạn chỉ có hai lựa chọn: hoặc là lấy nó (1 lần), hoặc là không lấy nó (0 lần). Mục tiêu là chọn các vật phẩm sao cho tổng giá trị đạt được là lớn nhất mà tổng cân nặng không vượt quá sức chứa của túi.

Bài toán Cái túi có giới hạn gần giống như vậy, nhưng có một điểm khác biệt quan trọng: với mỗi loại vật phẩm, bạn không chỉ có 0 hoặc 1 cái, mà bạn có thể lấy tối đa một số lượng nhất định của loại vật phẩm đó.

Phát biểu chính xác hơn: Cho một chiếc túi có sức chứa W. Cho N loại vật phẩm. Mỗi loại vật phẩm i có cân nặng w_i, giá trị v_i và số lượng tối đa có sẵn là q_i. Hãy chọn số lượng vật phẩm của mỗi loại (không vượt quá q_i và tổng cân nặng không vượt quá W) sao cho tổng giá trị đạt được là lớn nhất.

Ví dụ: Bạn đi siêu thị với một chiếc giỏ có sức chứa 10kg.

• Loại A: Chuối - 2kg/nải, 30k/nải, có sẵn 3 nải.
• Loại B: Táo - 1kg/túi, 20k/túi, có sẵn 5 túi.
• Loại C: Cam - 3kg/lưới, 50k/lưới, có sẵn 2 lưới.

Bạn muốn chọn bao nhiêu nải chuối, bao nhiêu túi táo, bao nhiêu lưới cam để tổng cân nặng không quá 10kg và tổng giá trị là lớn nhất?

So sánh với các biến thể khác

• 0/1 Knapsack: Mỗi vật phẩm duy nhất (chỉ có 1 cái của loại đó). Bounded Knapsack trở thành 0/1 Knapsack nếu q_i = 1 cho mọi loại vật phẩm i.
• Unbounded Knapsack (Bài toán cái túi không giới hạn): Mỗi loại vật phẩm có sẵn với số lượng vô hạn. Bounded Knapsack trở thành Unbounded Knapsack nếu q_i rất lớn (lớn hơn W / w_i cho mọi loại i, nghĩa là bạn không bao giờ hết hàng trước khi túi đầy).

Bài toán có giới hạn nằm ở giữa hai biến thể này, đòi hỏi một cách tiếp cận riêng biệt.

Cách tiếp cận ngây thơ (Naive Approach)

Ý tưởng đơn giản nhất để giải quyết bài toán có giới hạn là "biến" nó trở lại thành bài toán 0/1 Knapsack. Làm thế nào?

Nếu loại vật phẩm i có số lượng q_i, chúng ta có thể coi như có q_i vật phẩm riêng biệt của loại đó, mỗi vật phẩm có cân nặng w_i và giá trị v_i. Sau khi "nhân bản" tất cả các loại vật phẩm theo số lượng của chúng, chúng ta sẽ có một tập hợp lớn các vật phẩm đơn lẻ. Lúc này, bài toán trở thành: chọn các vật phẩm trong tập hợp mới này (mỗi cái chỉ lấy 0 hoặc 1 lần) để tối đa hóa giá trị trong giới hạn sức chứa W. Đây chính là bài toán 0/1 Knapsack trên một tập hợp vật phẩm lớn hơn.

Ví dụ minh họa (tiếp theo ví dụ siêu thị):

• Chuối (Loại A, 3 nải): coi như có 3 vật phẩm riêng biệt: Chuối_1 (2kg, 30k), Chuối_2 (2kg, 30k), Chuối_3 (2kg, 30k).
• Táo (Loại B, 5 túi): coi như có 5 vật phẩm riêng biệt: Táo_1 (1kg, 20k), Táo_2 (1kg, 20k), ..., Táo_5 (1kg, 20k).
• Cam (Loại C, 2 lưới): coi như có 2 vật phẩm riêng biệt: Cam_1 (3kg, 50k), Cam_2 (3kg, 50k).

Tổng cộng, thay vì 3 loại vật phẩm, giờ ta có 3 + 5 + 2 = 10 vật phẩm đơn lẻ. Giải bài toán 0/1 Knapsack với 10 vật phẩm này.

Ưu điểm: Dễ hiểu, sử dụng lại được giải thuật 0/1 Knapsack đã biết. Nhược điểm: Nếu số lượng q_i của một loại vật phẩm nào đó rất lớn, tổng số vật phẩm đơn lẻ sau khi "nhân bản" sẽ trở nên khổng lồ. Điều này làm cho giải thuật 0/1 Knapsack trở nên cực kỳ chậm và tốn bộ nhớ, do độ phức tạp phụ thuộc vào tổng số vật phẩm.

Rõ ràng, chúng ta cần một cách tiếp cận hiệu quả hơn khi q_i có thể lớn.

Cách tiếp cận hiệu quả: Quy hoạch động kết hợp Phân rã nhị phân (Binary Decomposition)

Điểm mấu chốt để giải quyết bài toán có giới hạn một cách hiệu quả nằm ở chỗ chúng ta có thể lấy nhiều đơn vị của cùng một loại vật phẩm. Cách tiếp cận hiệu quả nhất thường được sử dụng là kết hợp quy hoạch động (Dynamic Programming - DP) với kỹ thuật phân rã nhị phân (Binary Decomposition).

Ý tưởng chính: Thay vì coi q_i vật phẩm loại i là q_i vật phẩm riêng lẻ giống hệt nhau (cách ngây thơ), chúng ta sẽ "đóng gói" q_i vật phẩm này thành các gói (bundles) có kích thước dựa trên lũy thừa của 2.

Ví dụ, nếu bạn có 13 quả táo (số lượng q_i = 13), thay vì 13 quả táo riêng biệt, bạn có thể coi chúng như:

• Một gói 1 quả táo (2^0)
• Một gói 2 quả táo (2^1)
• Một gói 4 quả táo (2^2)
• Gói còn lại: 13 - (1 + 2 + 4) = 13 - 7 = 6 quả táo.

Tại sao lại làm như vậy? Bất kỳ số lượng nào từ 1 đến 13 đều có thể được tạo thành bằng cách tổng hợp các gói này. Ví dụ:

• Muốn 3 quả táo: lấy gói 1 và gói 2 (1+2=3)
• Muốn 5 quả táo: lấy gói 1 và gói 4 (1+4=5)
• Muốn 10 quả táo: lấy gói 4 và gói 6 (4+6=10)
• Muốn 13 quả táo: lấy gói 1, gói 2, gói 4, và gói 6 (1+2+4+6=13)

Bằng cách này, thay vì có 13 vật phẩm đơn lẻ của loại táo, chúng ta chỉ có 4 "gói" táo (gói 1, gói 2, gói 4, gói 6). Mỗi gói này là duy nhất (không thể lấy nhiều hơn 1 lần mỗi gói), và chúng ta có thể sử dụng DP cho bài toán 0/1 Knapsack trên tập hợp các gói này.

Quá trình thực hiện:

1. Phân rã Nhị phân (Binary Decomposition): Đối với mỗi loại vật phẩm i với số lượng q_i:

   • Tạo các gói có kích thước 1, 2, 4, 8, ... , 2^k sao cho tổng 1 + 2 + 4 + ... + 2^k <= q_i.
   • Mỗi gói có kích thước k sẽ có cân nặng k * w_i và giá trị k * v_i.
   • Số lượng còn lại sau khi trừ đi các lũy thừa của 2 (q_i - (1 + 2 + ... + 2^k)) sẽ tạo thành gói cuối cùng. Gói cuối cùng này có kích thước là số lượng còn lại, cân nặng là số lượng còn lại nhân w_i, giá trị là số lượng còn lại nhân v_i.
   • Tất cả các gói được tạo ra từ một loại vật phẩm ban đầu giờ đây được coi là các vật phẩm riêng biệt (chỉ lấy 0 hoặc 1 lần) trong một tập hợp mới.

2. Giải bài toán 0/1 Knapsack trên tập hợp gói mới: Sau khi phân rã tất cả các loại vật phẩm, chúng ta thu được một tập hợp mới gồm các "gói" vật phẩm. Mỗi gói có một cân nặng và một giá trị xác định, và chỉ có thể lấy 0 hoặc 1 lần. Bài toán trở thành bài toán 0/1 Knapsack cổ điển trên tập hợp các gói này với sức chứa W.

Chúng ta có thể giải bài toán 0/1 Knapsack này bằng Quy hoạch động với mảng 1 chiều để tối ưu bộ nhớ.

Mảng DP: dp[w] biểu diễn giá trị lớn nhất có thể đạt được với sức chứa w. Khởi tạo: dp[0...W] = 0. Lặp qua từng gói g trong tập hợp các gói đã phân rã:

• Với mỗi gói g có cân nặng w_g và giá trị v_g:
• Lặp qua sức chứa w từ W xuống đến w_g:
  • dp[w] = max(dp[w], dp[w - w_g] + v_g)

Lưu ý quan trọng: vòng lặp sức chứa w phải đi ngược từ W xuống khi sử dụng mảng DP 1 chiều cho bài toán 0/1. Điều này đảm bảo rằng khi tính dp[w], chúng ta sử dụng giá trị dp[w - w_g] từ trạng thái trước khi xét đến gói g, tránh việc sử dụng lại gói g nhiều lần trong cùng một tính toán (vì mỗi gói chỉ có 1 bản sao).

Sau khi lặp qua tất cả các gói, dp[W] sẽ là giá trị lớn nhất có thể đạt được với sức chứa W.

Ví dụ minh họa chi tiết bằng C++

Hãy áp dụng kỹ thuật này với một ví dụ cụ thể.

Bài toán: Sức chứa túi: W = 10 Các loại vật phẩm:

1. Item 1: w=2, v=3, q=3
2. Item 2: w=3, v=4, q=2
3. Item 3: w=4, v=5, q=1

Bước 1: Phân rã nhị phân

• Item 1 (w=2, v=3, q=3):

  • 2^0 = 1: gói 1 có kích thước 1. Còn lại: 3 - 1 = 2.
  • 2^1 = 2: gói 2 có kích thước 2. Còn lại: 2 - 2 = 0.
  • Ta có các gói: (kích thước 1, w=12=2, v=13=3) và (kích thước 2, w=22=4, v=23=6).
  • Gói 1: w=2, v=3
  • Gói 2: w=4, v=6

• Item 2 (w=3, v=4, q=2):

  • 2^0 = 1: gói 1 có kích thước 1. Còn lại: 2 - 1 = 1.
  • Lũy thừa tiếp theo 2^1 = 2 > còn lại là 1. Dừng.
  • Gói cuối cùng có kích thước bằng phần còn lại là 1.
  • Ta có các gói: (kích thước 1, w=13=3, v=14=4) và (kích thước 1, w=13=3, v=14=4).
  • Gói 3: w=3, v=4
  • Gói 4: w=3, v=4
  • Lưu ý: Mặc dù gói 3 và 4 có cùng (w,v), chúng là các "phiên bản" khác nhau từ quá trình phân rã, và trong bài toán 0/1 trên các gói này, chúng ta coi chúng là riêng biệt và chỉ lấy mỗi gói tối đa 1 lần.

• Item 3 (w=4, v=5, q=1):

  • 2^0 = 1: gói 1 có kích thước 1. Còn lại: 1 - 1 = 0.
  • Ta có gói: (kích thước 1, w=14=4, v=15=5).
  • Gói 5: w=4, v=5

Sau khi phân rã, chúng ta có tập hợp các gói mới cho bài toán 0/1 Knapsack:

• Gói 1: w=2, v=3
• Gói 2: w=4, v=6
• Gói 3: w=3, v=4
• Gói 4: w=3, v=4
• Gói 5: w=4, v=5

Tổng cộng 5 gói mới.

Bước 2: Giải bài toán 0/1 Knapsack với các gói

Sức chứa W = 10. Mảng DP dp[0...10], khởi tạo bằng 0.

dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Xét từng gói:

1. Gói 1 (w=2, v=3): Lặp w từ 10 xuống 2.

   • dp[10] = max(dp[10], dp[10-2] + 3) = max(0, dp[8] + 3)
   • ...
   • dp[2] = max(dp[2], dp[2-2] + 3) = max(0, dp[0] + 3) = 3
   • ... (Các giá trị khác được cập nhật nếu việc thêm gói này có lợi) Sau gói 1: dp có thể là [0, 0, 3, 3, 3, 3, 6, 6, 6, 6, 9] (ví dụ minh họa, cần tính toán đầy đủ)

2. Gói 2 (w=4, v=6): Lặp w từ 10 xuống 4.

   • dp[10] = max(dp[10], dp[10-4] + 6) = max(dp[10], dp[6] + 6)
   • ...
   • dp[4] = max(dp[4], dp[4-4] + 6) = max(dp[4], dp[0] + 6) = max(3, 0+6) = 6
   • ...

3. Gói 3 (w=3, v=4): Lặp w từ 10 xuống 3.

   • dp[10] = max(dp[10], dp[10-3] + 4) = max(dp[10], dp[7] + 4)
   • ...
   • dp[3] = max(dp[3], dp[3-3] + 4) = max(dp[3], dp[0] + 4) = max(3, 0+4) = 4
   • ...

4. Gói 4 (w=3, v=4): Lặp w từ 10 xuống 3.

   • dp[10] = max(dp[10], dp[10-3] + 4) = max(dp[10], dp[7] + 4)
   • ...
   • dp[3] = max(dp[3], dp[3-3] + 4) = max(dp[3], dp[0] + 4) = max(4, 0+4) = 4 (hoặc có thể thay đổi tùy thuộc vào giá trị dp[0] hiện tại)
   • ...

5. Gói 5 (w=4, v=5): Lặp w từ 10 xuống 4.

   • dp[10] = max(dp[10], dp[10-4] + 5) = max(dp[10], dp[6] + 5)
   • ...
   • dp[4] = max(dp[4], dp[4-4] + 5) = max(dp[4], dp[0] + 5) = max(6, 0+5) = 6
   • ...

Sau khi xử lý hết 5 gói, giá trị cuối cùng của dp[10] sẽ là đáp án.

Hãy xem code C++ chi tiết:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Cấu trúc biểu diễn một vật phẩm ban đầu (loại)
struct OriginalItem {
    int weight;
    int value;
    int quantity;
};

// Cấu trúc biểu diễn một gói (bundle) sau khi phân rã nhị phân
struct Bundle {
    int weight;
    int value;
    // Quantity là 1 cho các bundle, không cần lưu
};

// Hàm thực hiện phân rã nhị phân cho một loại vật phẩm ban đầu
vector<Bundle> binaryDecomposition(const OriginalItem& item) {
    vector<Bundle> bundles;
    int quantity = item.quantity;
    int k = 1; // Kích thước gói theo lũy thừa của 2

    // Tạo các gói có kích thước 1, 2, 4, ...
    while (quantity > 0) {
        int current_k = min(k, quantity); // Kích thước gói hiện tại
        bundles.push_back({item.weight * current_k, item.value * current_k});
        quantity -= current_k;
        k *= 2; // Lũy thừa tiếp theo của 2
    }
    return bundles;
}

// Hàm giải bài toán 0/1 Knapsack với một tập hợp các gói (mỗi gói chỉ lấy 0 hoặc 1 lần)
// Sử dụng DP O(Capacity) space
int solveZeroOneKnapsack(const vector<Bundle>& bundles, int capacity) {
    vector<int> dp(capacity + 1, 0);

    // Duyệt qua từng gói
    for (const auto& bundle : bundles) {
        int w = bundle.weight;
        int v = bundle.value;

        // Duyệt qua các mức sức chứa từ W xuống w
        // Đảm bảo mỗi gói chỉ được sử dụng 1 lần
        for (int c = capacity; c >= w; --c) {
            dp[c] = max(dp[c], dp[c - w] + v);
        }
    }

    return dp[capacity];
}

// Hàm chính giải bài toán Bounded Knapsack
int solveBoundedKnapsack(const vector<OriginalItem>& items, int capacity) {
    vector<Bundle> all_bundles;

    // Bước 1: Phân rã tất cả các loại vật phẩm thành các gói 0/1
    for (const auto& item : items) {
        vector<Bundle> bundles_from_item = binaryDecomposition(item);
        all_bundles.insert(all_bundles.end(), bundles_from_item.begin(), bundles_from_item.end());
    }

    // Bước 2: Giải bài toán 0/1 Knapsack với tập hợp các gói đã phân rã
    return solveZeroOneKnapsack(all_bundles, capacity);
}

int main() {
    // Ví dụ minh họa
    int capacity = 10;
    vector<OriginalItem> items = {
        {2, 3, 3}, // Item 1: w=2, v=3, q=3
        {3, 4, 2}, // Item 2: w=3, v=4, q=2
        {4, 5, 1}  // Item 3: w=4, v=5, q=1
    };

    int max_value = solveBoundedKnapsack(items, capacity);

    cout << "Suc chua tui: " << capacity << endl;
    cout << "Cac loai vat pham:" << endl;
    for (const auto& item : items) {
        cout << "- w=" << item.weight << ", v=" << item.value << ", q=" << item.quantity << endl;
    }
    cout << "\nGia tri lon nhat co the dat duoc: " << max_value << endl; // Expected output: 14

    // Giải thích ví dụ:
    // Phân rã:
    // Item 1 (w=2, v=3, q=3) -> Bundles: (w=2, v=3), (w=4, v=6)
    // Item 2 (w=3, v=4, q=2) -> Bundles: (w=3, v=4), (w=3, v=4)
    // Item 3 (w=4, v=5, q=1) -> Bundles: (w=4, v=5)
    // Tổng cộng các bundles: (2,3), (4,6), (3,4), (3,4), (4,5).
    // Áp dụng 0/1 Knapsack W=10:
    // Có thể chọn:
    // 1x Item 1 (3 nải chuối): 3 * (2kg, 30k) = (6kg, 90k) -> W=10, Value=90. Còn 4kg. Không đủ chỗ cho gói nào.
    // 1x Item 2 (2 túi táo): 2 * (3kg, 40k) = (6kg, 80k) -> W=10, Value=80. Còn 4kg. Có thể lấy gói (4kg, 60k) từ Item 1 -> (10kg, 80+60=140k)
    // 1x Item 1 (1 nải), 1x Item 2 (2 túi): 1* (2,3) + 2* (3,4) = (2kg, 30k) + (6kg, 80k) = (8kg, 110k). Còn 2kg. Không đủ cho gói nào.
    // Cách tối ưu: Lấy gói (w=4, v=6) từ Item 1 (tương đương 2 nải chuối), gói (w=3, v=4) từ Item 2 (tương đương 1 túi táo), và gói (w=3, v=4) từ Item 2 (tương đương túi táo thứ 2).
    // Tổng W = 4 + 3 + 3 = 10. Tổng V = 6 + 4 + 4 = 14.
    // Hoặc: Lấy gói (w=4, v=6) từ Item 1 (2 nải chuối), và gói (w=4, v=5) từ Item 3 (1 lưới cam).
    // Tổng W = 4 + 4 = 8 <= 10. Tổng V = 6 + 5 = 11. Còn 2kg, có thể thêm gói (w=2, v=3) từ Item 1 (1 nải chuối).
    // Tổng W = 8 + 2 = 10. Tổng V = 11 + 3 = 14.
    // Kết quả tối ưu là 14.

    return 0;
}

Giải thích mã nguồn C++

1. OriginalItem và Bundle Structs:

   • OriginalItem: Lưu trữ thông tin của một loại vật phẩm ban đầu: cân nặng weight, giá trị value, và số lượng quantity.
   • Bundle: Lưu trữ thông tin của một gói vật phẩm được tạo ra sau khi phân rã: cân nặng weight và giá trị value. Vì mỗi Bundle chỉ được lấy 0 hoặc 1 lần, chúng ta không cần trường quantity ở đây.

2. binaryDecomposition Function:

   • Hàm này nhận vào một OriginalItem và trả về một vector<Bundle>.
   • Nó triển khai kỹ thuật phân rã nhị phân. Bắt đầu với kích thước gói k=1.
   • Trong vòng lặp while (quantity > 0), nó tạo ra các gói có kích thước là lũy thừa của 2 (hoặc phần còn lại nếu nhỏ hơn).
   • current_k = min(k, quantity): Xác định kích thước thực tế của gói hiện tại. Nếu k (lũy thừa của 2) lớn hơn số lượng còn lại, thì gói cuối cùng sẽ có kích thước bằng số lượng còn lại.
   • bundles.push_back({item.weight * current_k, item.value * current_k});: Tạo một Bundle mới với cân nặng và giá trị tương ứng với kích thước current_k và thêm vào vector bundles.
   • quantity -= current_k;: Giảm số lượng còn lại.
   • k *= 2;: Chuyển sang lũy thừa tiếp theo của 2.
   • Vòng lặp tiếp tục cho đến khi quantity hết.

3. solveZeroOneKnapsack Function:

   • Hàm này nhận vào một vector<Bundle> (tập hợp các gói đã được phân rã) và sức chứa capacity, trả về giá trị lớn nhất đạt được bằng bài toán 0/1 Knapsack.
   • Đây là triển khai DP 1 chiều cho 0/1 Knapsack.
   • vector<int> dp(capacity + 1, 0);: Khởi tạo mảng DP có kích thước capacity + 1, tất cả giá trị ban đầu là 0. dp[w] sẽ lưu trữ giá trị lớn nhất cho sức chứa w.
   • Vòng lặp ngoài duyệt qua từng gói trong tập hợp bundles.
   • Vòng lặp trong duyệt qua các mức sức chứa c từ capacity xuống đến cân nặng w của gói hiện tại. Đây là điểm mấu chốt của DP 0/1 1 chiều: duyệt ngược giúp đảm bảo rằng khi tính dp[c], giá trị dp[c - w] được lấy từ trạng thái trước khi xem xét gói hiện tại, ngăn không cho gói hiện tại được sử dụng nhiều lần.
   • dp[c] = max(dp[c], dp[c - w] + v);: Cập nhật giá trị lớn nhất cho sức chứa c. Ta có hai lựa chọn:
     • Không lấy gói hiện tại: giá trị vẫn là dp[c] (giá trị tốt nhất đã đạt được trước khi xét gói này).
     • Lấy gói hiện tại: giá trị là dp[c - w] (giá trị tốt nhất cho phần sức chứa còn lại sau khi lấy gói) cộng thêm giá trị v của gói.

4. solveBoundedKnapsack Function:

   • Đây là hàm chính kết hợp hai bước.
   • Tạo một vector rỗng all_bundles để chứa tất cả các gói sau khi phân rã từ tất cả các loại vật phẩm ban đầu.
   • Lặp qua từng OriginalItem trong vector items.
   • Đối với mỗi item, gọi binaryDecomposition để nhận về các gói tương ứng.
   • Sử dụng all_bundles.insert(all_bundles.end(), bundles_from_item.begin(), bundles_from_item.end()); để nối (ghép) các gói mới tạo ra vào cuối danh sách all_bundles.
   • Sau khi phân rã hết, gọi solveZeroOneKnapsack với all_bundles và capacity để nhận kết quả cuối cùng.

5. main Function:

   • Thiết lập ví dụ: sức chứa và danh sách các loại vật phẩm với cân nặng, giá trị, số lượng.
   • Gọi solveBoundedKnapsack để tính toán.
   • In kết quả. Phần comment giải thích thêm về cách giải bài toán cụ thể với ví dụ đã cho, giúp người đọc dễ theo dõi quá trình suy luận.

Độ phức tạp thời gian của giải thuật này là O(Capacity sum(log q_i)), vì mỗi loại vật phẩm với số lượng q_i sẽ được phân rã thành khoảng log_2(q_i) gói, và sau đó chúng ta chạy DP 0/1 trên tổng số gói đó. Tổng số gói mới là khoảng sum(log q_i), và DP 0/1 tốn O(Số gói Capacity). Điều này hiệu quả hơn đáng kể so với cách tiếp cận ngây thơ khi q_i lớn.

Độ phức tạp không gian là O(Capacity) cho mảng DP và O(sum(log q_i)) để lưu trữ các gói đã phân rã.

Bài tập ví dụ:

Tổng tiền

Trong một ngày bận rộn tại ngân hàng, FullHouse Dev đang đối mặt với một thách thức thú vị. Họ được giao nhiệm vụ tính toán tất cả các cách có thể để tạo ra các mệnh giá tiền khác nhau từ những đồng xu có sẵn.

Bài toán

FullHouse Dev có \(n\) đồng xu với các mệnh giá khác nhau. Nhiệm vụ của họ là tìm ra tất cả các tổng tiền có thể tạo được từ những đồng xu này.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(n\) - số lượng đồng xu.
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, ..., x_n\) - mệnh giá của các đồng xu.

OUTPUT FORMAT:

• Dòng đầu tiên in ra số nguyên \(k\) - số lượng tổng tiền khác nhau có thể tạo được.
• Dòng thứ hai in ra tất cả các tổng tiền có thể theo thứ tự tăng dần.

Ràng buộc:

• \(1 \leq n \leq 100\)
• \(1 \leq x_i \leq 1000\)

Ví dụ

INPUT

4
4 2 5 2

OUTPUT

9
2 4 5 6 7 8 9 11 13

Giải thích

Với các đồng xu mệnh giá 4, 2, 5, 2, FullHouse Dev có thể tạo ra 9 tổng tiền khác nhau:

• 2 (sử dụng một đồng 2)
• 4 (sử dụng hai đồng 2 hoặc một đồng 4)
• 5 (sử dụng một đồng 5)
• 6 (sử dụng ba đồng 2)
• 7 (sử dụng một đồng 5 và một đồng 2)
• 8 (sử dụng bốn đồng 2)
• 9 (sử dụng một đồng 5 và hai đồng 2)
• 11 (sử dụng một đồng 5 và ba đồng 2)
• 13 (sử dụng một đồng 5 và bốn đồng 2)

Làm thêm nhiều bài tập miễn phí tại đây