Chotchkies Restaurant [duplicate]

Question

Because there isn't enough xkcd on PPCG...

Challenge

The challenge is the same as above - given a menu and a total price, you need to find what the customer ordered.

The menu will be supplied as a text file in the format:

Name:Price
Name:Price

The path to the menu file and the total price should be supplied via argv or STDIN. If you wish, the menu may be supplied via STDIN/argv (instead of newlines, separate each item by commas).

The output should be a list of values. If there are multiple answers, output all of them.

Example

Menu:

Burger:12.60
Pepsi:3.50
Lobster Thermidore:33.10
Ice Cream:23.00

Total Price: 68.70

The output is:

Burger
Lobster Thermidore
Ice Cream

Winning

The fastest code given an undisclosed problem wins. The speed will be taken five times and averaged.

Answer 1

Python 2 - Naive implementation - 224

Well, let's start with "the most naive algorithm" as some kind of reference solution:

import itertools

path = input()
total = input()

with open(path) as f:
    menu = map(lambda l: l.split(':'), f.read().split('\n'))

names, prices = zip(*menu)
prices = map(float, prices)

for i in range(len(menu)):
    for comb in itertools.combinations(range(len(menu)), i):
        if sum(prices[c] for c in comb) == total:
            for i in comb:
                print names[i] 

Input:

"data.txt"
68.70

Output:

Burger
Lobster Thermidore
Ice Cream

Complexity:

O(2^N * N)

--> exponential in the number of menu items N (of course)

---

Edit:

To reflect the new winning criterion I golfed it down quite a bit:

from itertools import*
S=str.split
f,t=S(input())
m=[S(l,':')for l in S(open(f).read(),'\n')]
R=range(len(m))
F=float
for i in R:
 for C in combinations(R,i):
  if sum(F(m[c][1])for c in C)==F(t):
   for j in C:print m[j][0]

The input format changed to data.txt 68.70 (both on one line separated with a whitespace).