Optimized output from the python dictionary

Question

I am having very difficult time to solve one of the programming puzzle. I have a dictionary which has items (denoted by i#) and value as price of the item.`Items can be combined to form combo package.

{('i2', 'i3'): '4', ('i1',): '1',('i1', 'i3', 'i4'): '6.5', ('i3',): '3',('i1', 'i2', 'i3'): '4.5', ('i2',): '2', ('i4',): '4'}

I want to return minimum price for given input items. User will not have any issue if he gets extra item in minimum price from combo package:

1. For input i1, it should return price 1. (Which is minimum price of all i1 item)
2. For input (i1,i2), should return 3.
3. For input (i1,i2,i3,i4), should return 8.5
4. For input (i1,i1,i2,i3,i4), should return 9.5

Does anyone have any idea how to proceed with it ? Which algorithm to use ?

Thanks, Sunil

Answer 1

Use itertools.combinations() to generate combinations of x packages. Then, check for each of the combinations if they include the required items, and find the valid combo with the lowest price.

To find all the combinations of 4 different packages of items:

d = {('i2', 'i3'): '4', ('i1',): '1',('i1', 'i3', 'i4'): '6.5', ('i3',): '3',
     ('i1', 'i2', 'i3'): '4.5', ('i2',): '2', ('i4',): '4'}
from itertools import combinations
combos = list(combinations(d, 4)) # you should try combos of different lenghts, 
                                  # from 1 to the number of desired items

For illustration, let's look at one of the combos. print combos[0] gives:
(('i2', 'i3'), ('i1',), ('i1', 'i3', 'i4'), ('i3',))

And to get the price of this combo:

sum([float(d[item]) for item in combos[0]])

Which gives 14.5

I leave it to you to find the cheapest suitable combo :)