Đề bài:

Cửa hàng nhà Tèo bán hàng sử dụng cân đĩa thăng bằng. Có $n$ quả cân đánh số từ $1$ đến $n$, quả thứ $i$ có khối lượng là $w_i$. Khi cần cân một mặt hằng nào đó, Tèo sẽ đặt mặt hàng cần cân lên một bên đĩa và chọn một số quả cân đặt lên đĩa còn lại sao cho cân thăng bằng, tổng khối lượng của những quả cân đặt trên đĩa sẽ là khối lượng của mặt hàng cần cân.

Nhà Tèo hiện đang bán $m$ mặt hàng đánh số từ $1$ đến $m$, mặt hàng thứ $i$ có khối lượng là $v_i$ (Đấy là Tèo biết vậy thôi chứ khi bán vẫn phải cân cho khách hàng xem). Em hãy giúp bạn Tèo tính toán xem những mặt hàng nào có thể cân được nhé.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương $n$ và $m$;
• Dòng thứ hai chứa $n$ số nguyên dương $w_1, w_2,..., w_n$ là khối lượng của $n$ quả cân;
• Dòng thứ ba chứa $m$ số nguyên dương $v_1, v_2,... v_m$ là khối lượng của mặt hàng.

Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

• Ghi ra một xâu độ dài $m$, ký tự thứ $i$ là $1$ nếu mặt hàng thứ $i$ có thể cân được và là $0$ nếu mặt hàng thứ $i$ không thể cân được.

Ví dụ:

//Input
3 4
1 2 5
1 2 3 4

//Output
1110

Giới hạn:

• $1 <= n <= 20; 1 <= m <= 10^5; 1 <= w_i, v_i <= 10^6$

Nhận xét:

• Để kiểm tra, ta sẽ liệt kê hết tất cả các tổng có thể xây dựng được từ các phần tử của mảng $w$ và đánh dấu chúng, khi xét đến mảng $v$ thì chỉ cần kiểm tra lại, nếu tồn tại một tổng được xây dựng có giá trị bằng với $v_i$ thì in ra $1$, ngược lại in ra $0$.
• Ta thấy nếu một số $j - w_i$ là tổng có thể xây dựng được từ các phần tử của mảng $w$ thì $j$ cũng là tổng có thể xây dựng được từ các phần tử của mảng $w$.Vì vậy, gọi $f[j]$ là phần tử lưu giá trị $0$ nếu $j$ không thể tạo lập từ các phần tử của mảng $w$, $1$ nếu ngược lại, ta có công thức QHĐ như sau: $$\begin{cases} f[0] = 1 \\ f[j] = 1 &\text{if } f[j - w[i]] = 1 (1 <= i <= n) \end{cases}$$

Full code:

#include <bits/stdc++.h>
using namespace std;
int n, m, w[25], c[100005], t;
bool f[2000005];
int main()
{
    cin >> n >> m;
    for (int i = 1; i<=n; i++)
    {
        cin >> w[i];
        t = t + w[i];
    }
    for (int j = 1; j<=m; j++)
        cin >> c[j];

    f[0] = 1;
    for (int i = 1; i<=n; i++)
        for (int j = t; j>= w[i]; j--)
            if (f[j - w[i]] == true) f[j] = true;

    for (int i = 1; i<=m; i++)
        if (f[c[i]] == true) cout << 1; //Kiểm tra, nếu tổng c[i] tồn tại thì in ra 1, ngược lại in ra 0
    else cout << 0;
    return 0;
}

Nguồn bài tập

Thiết kế giải thuật