XKCD NP-COMPLETE

gistfile1.py

#!/usr/bin/python3
import math
import itertools
     
APPETIZERS = {
    "Mixed Fruit"       : 215,
    "French Fries"      : 275,
    "Side Salad"        : 335,
    "Hot Wings"         : 355,
    "Mozzarella Sticks" : 420,
    "Sampler Plate"     : 580
}
TARGET_PRICE = 1505
MAX_ITEMS    = math.ceil(TARGET_PRICE / min(APPETIZERS.values()))
 
def getPrice(items):
    totalPrice = 0
    for item in items:
        totalPrice += APPETIZERS[item]
    return totalPrice  
 
def getCombos(size):
    return itertools.combinations_with_replacement(APPETIZERS.keys(), size)
     
def main():
    for i in range(1, MAX_ITEMS+1):
        for combo in getCombos(i):
            if getPrice(combo) == TARGET_PRICE:
                print(combo)
     
if __name__ == "__main__":
    main()