# CSES Elevator Rides | Đi thang máy
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Author : Lê Việt Tín

## Spoiler Alert

### Approch 1 (brute-force)
- Duyệt bằng cách phân nhóm bằng backtracking (đệ quy)
#### Ý tưởng
- Thử từng người, xem có thể đưa họ vào nhóm hiện tại không
- Nếu nhóm đầy, bắt đầu một nhóm mới
- Tìm phương án ít lượt nhất
---
Code

    //#pragma GCC optimize("O2")
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    int n, x;
    vector<int> w;
    int best = LLONG_MAX;
    void backtrack(int i, vector<int> &rides, vector<int> &weight) {
        if (i == n) {
            best = min(best, (int)rides.size());
            return;
        }
        // thêm người thứ i vào chuyến đã có
        for (int j = 0; j < rides.size(); j++) {
            if (weight[j] + w[i] <= x) {
                weight[j] += w[i];
                backtrack(i + 1, rides, weight);
                weight[j] -= w[i];  // đệ quy
            }
        }
        // Mở chuyến mới
        rides.push_back(i);
        weight.push_back(w[i]);
        backtrack(i + 1, rides, weight);
        rides.pop_back();
        weight.pop_back();
    }
    signed main() {
        cin >> n >> x;
        w.resize(n);
        for (int &wi : w) cin >> wi;
        vector<int> rides, weight;
        backtrack(0, rides, weight);
        cout << best;
        return 0;}

Độ phức tạp $O(2^n)$
### Approch 2
Tối ưu với Bitmask DP
#### Ý tưởng:
- Sử dụng Bitmask DP để lưu trạng thái tốt nhất khi xét tập hợp con của người
- `dp[mask] = {số chuyến ít nhất, trọng lượng chuyến cuối cùng}.`

//#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x;
vector<int> w;
pair<int, int> dp[1 << 20];
signed main() {
    cin >> n>>x;w.resize(n);
    for (int i = 0; i < n; i++) cin >> w[i];
    dp[0] = {1, 0};
    for (int mask = 1; mask < (1 << n); mask++) {
        dp[mask] = {n + 1, 0};
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                int prev = mask ^ (1 << i);
                auto [rides, we] = dp[prev];
                if (we + w[i] <= x) dp[mask] = min(dp[mask], {rides, we + w[i]});
                else dp[mask] = min(dp[mask], {rides + 1, w[i]});
            }
        }
    }
    cout << dp[(1 << n) - 1].first;
    return 0;
}

Độ phức tạp : $O(n*2^n)$
Question : bài này có thể giải theo cách nào khác không ?