Can't understand why my implementation of Itertools.combinations_with_replacement is not working correctly

Question

Cannot figure out why my code will not output the correct results of the itertools.combinations_with_replacement if for certain small values.

from itertools import combinations_with_replacement
menu = []
with open("menu.txt") as f:
    for line in f:
        budget = float(line.split("$")[-1])           # extract the budget
        break
    for line in f:                      
        itemName = line.split(",")[0]
        itemPrice = float(line.split("$")[-1])
        menu.append([itemName,itemPrice])
def shorten_list(menu):   # function to filter out items where price > budget
    i=0;                                
    for item in menu:
        if item[-1] > budget:
            del menu[i]
        i = i + 1
    return menu
shorten_list(menu)          #call to shorten_list function
for item in menu:
    item[-1] = int(item[-1]*100)    # cast to int to avoid floating point imprecision errors

budget = int(budget *100)     # cast to int to avoid floating point imprecision errors
flag = 0       # set a flag = 0 to check if solutions will be found
num_comb = 1
comb = [c for i in range(len(menu)+1) for c in combinations_with_replacement(menu, i)]      # outputs iterator with all possible combinations
print("\n")
for e in comb:
    if sum(l[1] for l in e) == budget:                  # filters out only the combinations that == our budget
        print ("Combination_with_R number " + str(num_comb)  + " is:") 
        print ([l[0] for l in e])                       # print only the item name
        print ("\n")
        num_comb += 1 
        flag = 1                        # if an solutions found we set flag = 1
    if flag == 0:           # if no solutions found, flag = 0 has not changed 
    print ("There is no combination of dishes that will equal your budget... Leave the change as tip! \n\n ")

The problem that I am having with the code is mostly when I need a combination to repeat a certain menu item to create a meal. For example if we have the menu item bread,$1.00 and the budget = 18 there should be a combination ['bread', 'bread','bread','bread'..... n=18] so essentially 18 breads. Or if the item is ketchup_packet,$0.10 and budget = 18 there should also be a combination of ['ketchup_packet',............ n = 180]. Assume that menu.txt is in this format:

$18.00
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80
pasta3,$5.05
salad,$3.25
pasta10,$10.10
pasta1,$2.65
TESTER,$1.20

For some reason with this menu.txt it won't output a combination of ['TESTER', 'TESTER',..... N =15]

But if the menu.txt is:

$12.00
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80
pasta3,$5.05
salad,$3.25
pasta10,$10.10
pasta1,$2.65
TESTER,$1.20

It will correctly output all combinations including ['TESTER','TESTER',..... n = 12]

It should also work with

$12.00
mixed fruit,$2.15
    french fries,$2.75
    side salad,$3.35
    hot wings,$3.55
    mozzarella sticks,$4.20
    sampler plate,$5.80
    pasta3,$5.05
    salad,$3.25
    pasta10,$10.10
    pasta1,$2.65
    TESTER,$0.01

But does not! Cannot understand why.

Answer 1

I cleaned up the code formatting, factored out a bunch of utility functions, and converted it to a linear programming problem. See what you think:

from decimal import Decimal

def get_name(s):
    return s.split(',')[0]

def get_price(s):
    return Decimal(s.split('$')[-1])

def get_menu(fname):
    with open(fname) as inf:
        budget = get_price(inf.next())
        items = [(get_name(line), get_price(line)) for line in inf]
    return budget, items

def integer_linear_solver(coefficients, total, index=None):
    """
    Given coefficients [c0, c1, ... cN] and total,
    generate all integer solutions to the equation
        s0*c0 + s1*c1 + ... + sN*cN == total
    and return as [s0, s1, ... sN]
    """
    if index is None:
        # Start at the end and work back
        # (this avoids having to repeatedly slice coefficients)
        index = len(coefficients) - 1

    c = coefficients[index]
    max_s = total // c

    if index:  # more coefficients available - recurse
        for s in range(max_s + 1):    # [0 .. max_s]
            for sol in integer_linear_solver(coefficients, total - s*c, index-1):
                yield sol + [s]
    else: # last coefficient
        if not(total % c):
            # no remainder -> exact solution found
            yield [max_s]

def print_sol(coeffs, labels):
    items = ('{0} {1}'.format(c, l) for c,l in zip(coeffs, labels) if c > 0)
    print(', '.join(items))

def main():
    budget,items = get_menu('menu.txt')
    names,prices = zip(*items)

    solutions = 0
    for sol in integer_linear_solver(prices, budget):
        print_sol(sol, names)
        solutions += 1

    if solutions:
        print('{} solutions found'.format(solutions))
    else:
        print("There is no combination of dishes that will equal your budget.")

if __name__=="__main__":
    main()

Run against your first example menu, it gives

2 side salad, 2 hot wings, 1 mozzarella sticks
2 french fries, 2 side salad, 1 sampler plate
1 mixed fruit, 3 side salad, 1 sampler plate
...
1 mixed fruit, 1 pasta1, 11 TESTER
15 TESTER
109 solutions found

Answer 2

comb = [c for i in range(len(menu)+1) for c in combinations_with_replacement(menu, i)]

This allows a number of items equal to at most the number of things in the menu. It will never buy more burgers than the menu has options.