5
Tôi nghĩ rằng điều này có thể là NP-complete, nhưng tôi sẽ hỏi anyway. Các thuật toán tham lam dường như không hoạt động trong đầu tôi.Thuật toán để tìm số lượng thẻ ít nhất bao gồm tất cả các mục?
Cho một tập hợp các mục, mỗi mục có 1 hoặc nhiều thẻ, tôi muốn tìm tập hợp thẻ nhỏ nhất bao gồm tất cả các mục.
Chỉnh sửa: Xem my "solution" here.
chỉ để tham khảo, thuật toán ngây thơ là n * 2^k. chỉ cần lặp qua bộ nguồn của các thẻ và kiểm tra xem mỗi mục được gắn thẻ có được bao phủ bởi tập hiện tại hay không. n là số lượng các mục được gắn thẻ, k là số lượng thẻ. – aaronasterling
vì vậy ... cho 1000 mục và 3000 thẻ ... Tôi đang xem các hoạt động 1.2e906 ... tức là, không thể giải quyết được ... rất nhiều cho kế hoạch đó. – mpen
@Mark, cách ngây thơ nhất để có được giải pháp tối ưu là n * 2^k. Tôi không chắc chắn về cách tốt hơn mặc dù. Nếu bạn chỉ muốn một xấp xỉ, nó có lẽ có thể được cải thiện tốt hơn thế. – aaronasterling