I am looking for a formal name and an algorithmic approach to the following problem.
Given is a set of services each coming with a price:
- {s1, 300}
- {s2, 400}
- {s3, 800}
Additionally there is a set of servicepackages each with a price that may differ from the total cost of the individual services:
- {p1, {s1, s2}, 600}
- {p2, {s2, s3}, 1050}
- {p3, {s1, s3}, 950}
- {p4, {s1, s2, s3}, 1250}
Now given a list of services (each service may appear many times) you want performed find the combination of packages and individual services with the lowest price. You can only use a package if you can completely fill it with services. A package may be ordered many times.
For example: Services to order :{s1,s2,s1,s3,s2,s3,s1}
possible Solutions:
- {p4, p4, s1} : 2800
- {p1, p1, p3, s3} : 2950
In this case the first solution would be the winner.
An exhaustive approach will quickly explode because it is O(n!) or even worse.
What is the formal name of this problem (if there is one)? How would you algorithmically approach that problem for hundreds of services and packages?