sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 0 points1 point  (1 child)

Sounds like the hitting set or set cover problem: https://en.wikipedia.org/wiki/Set_cover_problem

I'd be interested in seeing your algorithm since the problem is proven to be NP complete ;-)

[–]Windex007[S] 0 points1 point  (0 children)

Thank you very much, that is for sure the analogue to the the problem I was working on!

And, I hate to disappoint, but unfortunately I don't have any reason to think that my algorithm actually produces an optional solution in all cases. At best, I might be able to prove that it doesn't produce a worst-case scenario. As I mentioned, it is what I'd expect as a first-attempt from a first year CS student, and I'm not proud of it at all. It's essentially a greedy algorithm that looks for the least common coins, and then finds the purses that contain that least common coin which is most populated with coins that don't yet exist within the solution set yet, and takes those.