CODEWITHSUNDEEP
pythonalgorithmsetcover
Stavros Korokithakis
Stavros Korokithakis

Reputation: 4946

An optimal algorithm for the weighted set cover issue?

Sorry about the title, SO wasn't allowing the word "problem" in it. I have the following problem:

I have packages of things I want to sell, and each package has a price. When someone requests things X, Y and Z, I want to look through all the packages, some of which contain more than one item, and give the user the combination of packages that will cover their things and have the minimal price.

For example, I might suggest [(X, Y), (Z, Q)] for $10, since [(X), (Y), (Z)] costs $11. Since these are prices, I can't use the greedy weighted set cover algorithm, because two people getting the same thing for different prices would be bad.

However, I haven't been able to find a paper (or anything) detailing an optimal algorithm for the weighted set cover problem. Can someone help with an implementation (I'm using Python), a paper, or even a high-level description of how it works?

The packages I have are in the hundreds, and the things are 5-6, so running time isn't really an issue.

Thanks!

Upvotes: 0

Views: 1800

Answers (1)

Thomash
Thomash

Reputation: 6379

If you want an exponential algorithm, just try every subset of the set of packages and take the cheapest one that contains all the things you need.

Upvotes: 2

Related Questions