$\Huge\text{Market Solution}$

----------

:::info
🔗 Links:
📌 Tags: `DP`
✍ Writer: Hoàng Việt
📄 Content:
[TOC]
:::

---------

## Thuật toán

Cho $dp[i][S]$ lưu các giá trị $true/false$, với $dp[i][S]$ == $true$ thì có thể chọn ra được một tập con có tổng đúng bằng $S$ khi xét các phần tử từ $1$ đến $i$ ($i$ phần tử đầu tiên).

Bài toán cơ sở: $dp[0][0] = true$.

Có hai trường hợp chuyển trạng thái:

- $dp[i][S]$ |= $dp[i - 1][S]$, trường hợp không sử dụng phần tử thứ $i$.
- $dp[i][S]$ |= $dp[i - 1][S - a[i]]$, trường hợp có sử dụng phần tử thứ $i$.

Số lượng tổng tối đa có thể tạo được là số lượng $dp[n][S]$ == $true$.

Độ phức tạp $O(n^2 * a_i)$.

Code mẫu:

#include <bits/stdc++.h>

#define ll long long 
#define fi first 
#define se second 

using namespace std;

const int MAXN = 510;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int base = 28;

void solve() {
    int n; 
    cin >> n;

    int a[n + 1], S = 0;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
        S += a[i];
    }

    bool dp[n + 1][S + 1];
    memset(dp, false, sizeof(dp));

    dp[0][0] = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= S; j ++) {
            dp[i][j] |= dp[i - 1][j];
            if(j >= a[i] && j - a[i] <= S) 
                dp[i][j] |= dp[i - 1][j - a[i]];
        }

    int ans = 0;
    for(int i = 1; i <= S; i ++)
        ans += dp[n][i];

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // int tt;
    // cin >> tt;
    // while(tt --)
        solve();

    return 0;
}

------------