Fixed size thiết lập để chứa số lượng tối đa của bộ trao

Question

Tôi có khoảng 1000 bộ kích thước < = 5 số có chứa từ 1 tới 100.

{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... 

Có thể tìm thấy một tập hợp các kích thước 20 có chứa các số lượng tối đa các tập hợp đã cho?

Kiểm tra mỗi 100!/(80!*20!) bộ, không hiệu quả.

Answer 1

Tôi không chắc là NP này đã hoàn thành chưa.

Hãy xem xét các vấn đề liên quan đến nơi mà chúng tôi nhận được một phần thưởng của x cho mỗi bộ, nhưng phải trả một mức giá của y đối với mỗi số mà chúng ta muốn cho phép. (Một bộ chỉ trả phần thưởng nếu tất cả các số nó chứa đã được trả tiền cho.)

Bạn có thể giải quyết vấn đề kiểu này bằng cách sử dụng max flow algorithm bởi:

1. Thiết lập một nút nguồn
2. Setting lập một node đích
3. thiết lập một nút cho mỗi thiết
4. thiết lập một nút cho mỗi số
5. Thêm cạnh từ nguồn tới mỗi bộ có công suất x
012.
6. Thêm cạnh từ mỗi số để dest với công suất y
7. Đối với mỗi số một trong bộ s, thêm cạnh từ s đến một với công suất vô hạn

Giải quyết các luồng cực đại trên đồ thị này (từ nguồn đến nút đích) tìm thấy chi phí cắt giảm tối thiểu c.

Số tiền ròng chúng tôi sẽ thực hiện sẽ là N.x-c (trong đó N là số bộ).

Nếu chúng ta có thể chọn y (ví dụ bằng cách chia làm hai đoạn) như vậy mà chúng tôi đã lựa chọn chính xác 20 con số, sau đó chúng tôi đã được quản lý để giải quyết cho số lượng tối đa bộ với 20 con số.