Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

---Grigor---'s blog

By ---Grigor---, history, 2 years ago, In Russian,

Здравствуйте друзья,

На практике возникла подобная задача, нуждаюсь в помощи. Подскажите, пожалуйста, как бы вы решили?

Даны множество людей и множество предметов. Каждый человек имеет определенное количество денег, каждый предмет имеют свою стоимость. Все значения целочисленны. Может ли это множество людей купить все имеющиеся предметы?

Каждый человек может купить сколько угодно предметов (если хватает денег), каждый предмет может быть куплен только одним человеком.

Я думал решать через поток в двудольном графе, но не знаю как запретить наличие частично насыщенных ребер в результирующем потоке.

Заранее благодарю!

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

It can be reduced to the knapsack problem. Suppose the total cost of all things is S. We want to solve the knapsack problem for the maximum cost Y. There is a subset of cost at least X which is less than Y, if and only if 2 people which have Y and S — X money can buy all things. So by using binary search on X, we can find the maximum X and hence solve the knapsack problem. Your problem is NP complete even for 2 people.