Chotchkies Restaurant
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).