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