Buying subsets

Revision en1, by dpasztor, 2019-12-26 10:57:25

There is a set of items. You are given some subsets of these items. (each has a given price)

You should calculate how much money you need to spend to have a full set and which subsets you need to buy.

(Number of subsets is <= 3000)

(It is not guaranteed that there is a solution)

Easier version: You know that the main set is {1,2,3,4,5,6,7,8,9,10,11,12,13}

Example for easier version:

1,2,3 price: 3

4,5,6 price: 3

7,8,9 price: 3

10,11,12 price: 3

13 price: 100

1,2,3,4,5,6,7,8,9,10,11,12,13 price: 110

The answer is obviously 110. (you only need to buy a last one, they dont have to be proper subsets)

Does anybody know the solution? Is something similar here on CF?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dpasztor 2019-12-26 10:57:25 735 Initial revision (published)