0

(sorry for my english) I need find best price of products packages. Example items packages and prices: 

A=12
B=2
C=5
D=11
A+B=11
C+B=4
etc..

Now customer buy A,B,C. How can i find best combination price? For example brute force:

(A+B)+(c) = (11)+(5) = 16 or 
(A)+(B)+(C) = (12)+(2)+(5)=18 or
(A)+(B+C) = (12)+(4)=16
.enter code here
.
.

etc. How find best prices combination?

I tryed bruteforce and it workd but it was very slow.

jww
  • 97,681
  • 90
  • 411
  • 885
david rosko
  • 123
  • 7
  • 1
    Can you post your brute-force solution? (Sometimes one person's "brute force" actually has a lot of optimizations, and better algorithmic complexity, than another person's. And that will also give us an idea of what kind of notation you're looking to use. In fact, you say that your approach was "very slow", which suggests that you might even be using a real language?) – ruakh Feb 24 '15 at 00:20
  • 2
    Also, it would be helpful to know a little bit about the parameters. I.e. are packages always tuples of 2, or can they be more complicated like A+B+C, A+C+E+F, etc.? Is there a limit to the number of things you can pick at once? Cool problem! – wilkesybear Feb 24 '15 at 00:22
  • 1
    also similar to http://stackoverflow.com/questions/21427278/selecting-a-combination-of-minimum-cost – hatchet - done with SOverflow Feb 24 '15 at 00:35
  • @hatchet: Good finds! That second one may look like a more-complicated problem, but its accepted answer demonstrates that even *this* problem is NP-hard. – ruakh Feb 24 '15 at 00:48
  • It's an NP-hard problem, but a MIP solver will make quick work of it in practice. – David Eisenstat Feb 24 '15 at 00:56
  • @ruakh - yes, and given that the problem in this question is essentially the Set Cover Problem, proposing a good heuristic solution requires more detail (the boundaries of the problem) than the question has so far provided. – hatchet - done with SOverflow Feb 24 '15 at 00:59

0 Answers0