Ta sẽ phát biểu lại bài toán dưới dạng bài toán cái túi: Có ~n~ vật và mỗi vật có trọng lượng là ~t_i~, hãy chia các vật ra các túi sao cho trọng lượng của túi nặng nhất là nhỏ nhất

Giả sử đáp án của bài toán là ~max~.

Gọi ~F[mask]~ là số túi nhỏ nhất để chứa hết toàn bộ các con trong ~mask~ sao cho mỗi túi chỉ có trọng lượng tối đa là ~max~

~\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ F[mask] = min(F[submask]) + 1~

Với ~submask~ là phần ~xor~ hợp lệ của các ~mask~ con và ~mask~ (nghĩa là tổng trọng lượng của các con trong phần ~xor~ phải nhỏ hơn ~max~)

Vậy đáp án bài toán chính là ~max~ nhỏ nhất sao cho ~F[2^n - 1] \le k~

Độ phức tạp: ~O(3^n * log_2(sum(t_i)))~

Xem thêm về kĩ thuật duyệt ~mask~ con: all-submask

Code mẫu

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<int, int>;

#define fi first
#define se second
#define pb push_back
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }

const int N = 1e6 + 7, oo = 1e9 + 7;

int n, k, t[N], f[N];

bool check(int m, int mx) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        if (getBit(m, i)) sum += t[i];
    return sum <= mx;
}

int dp[15][N];
int calc(int mid) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= mid; j++) {
            dp[i + 1][j] = dp[i][j];
            if (j >= t[i]) maximize(dp[i + 1][j], dp[i][j - t[i]] + t[i]);
        }
    return dp[n][mid];
}

bool good(int mid) {
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int m = 0; m < (1 << n); m++)
        for (int s = m; ; s = (s - 1) & m) {
            if (check(s ^ m, mid)) {
                minimize(f[m], f[s] + 1);
            }
            if (!s) break;
        }
    return (f[(1 << n) - 1] <= k);
}

int main() {
//#ifndef ONLINE_JUDGE
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
//#endif
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &t[i]);
    ll l = 0, r = 1e6;
    while (l <= r) {
        ll mid = l + r >> 1;
        if (good(mid)) r = mid - 1; else l = mid + 1;
    }
    printf("%d", calc(r + 1));
}