Tìm số tiền tối thiểu thứ k của mỗi tập hợp con có thể

Question

Lần cuối cùng tôi tìm thấy vấn đề thú vị và tôi bị kẹt trên đó.

Cho số n a [1], ..., a [n] theo thứ tự tăng dần và số k (1 < = n, k < = 10^5).

Giả sử chúng tôi sắp xếp mọi tập hợp con có thể của chuỗi đã cho theo tổng.
Chúng ta phải tìm tổng của tập hợp con thứ k.

Ví dụ:
n = 4, k = 8
a = {2, 7, 8, 15}

1: {2}, tổng = 2
2: { 7}, tổng = 7
3: {8}, tổng = 8
4: {2, 7}, tổng = 9
5: {2, 8}, tổng = 10
6: {7, 8}, tổng cộng = 15
7: {15}, sum = 15
8: {2, 15}, tổng = 17
...
k = 8, vì vậy hãy trả lời = 17 (tập con {2,15}).

Tất nhiên chúng ta có thể tạo ra mọi tập con có thể và toàn bộ giải pháp chạy trong O (2^n * n), nhưng tôi đang tìm kiếm thứ gì đó thông minh hơn, hoặc ít nhất là O (nk).

Answer 1

(Đi giả tập con không rỗng cho đơn giản. Xử lý các tập hợp con trống là một hoặc hai dòng.)

Cho một tập hợp con khác rỗng của chỉ số S, xác định trẻ em của S là S \ {max(S)} U {max(S) + 1} và S U {max(S) + 1}. Bắt đầu với {1}, quan hệ con tạo thành một cây bao gồm mọi tập hợp con không phải là số nguyên dương.

{1} 
| \ 
{2} {1,2}______ 
| \  \  \ 
{3} {2,3} {1,3} {1,2,3} 

Được khóa bởi tổng các phần tử mảng tương ứng, cây này là một phần nhỏ. Nếu bạn tính toán các phím một cách cẩn thận (bằng cách cộng và trừ thay vì tổng hợp từ đầu) và thực hiện xóa bỏ min-heap một cách uể oải, thì bạn sẽ nhận được thuật toán O (k log k) -time.