Блог пользователя dpasztor

Автор dpasztor, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Maybe it's mincost max flow (mb there is easier solution, idk).

I also don't know if this solution will pass the time limit.

For example A is origin, B is sink, Si — subset no. i.

  • Add edges like A->Si with capacity=inf, cost=Si_price
  • Add edges Si->(items in Si) with capacity=1, cost=0
  • Add edges items->sink: capacity=1, cost=0

Max flow should be |items| if there is an answer, minimal cost will be the minimal price.

»
5 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

This is a harder version of set cover problem and therefore is np hard. The easier version can be solved using bitmasks.