Naiv udregner til Lagkagehusets bon-kringle - finder en samling af dine gl boner der rammer 1000 kr tættest

lagkagehuset-bon.py

bons =  list(reversed(sorted([64,38,69,73,73.5,57.50,74.50,222,73,91,172,39,94,140,130,56.50,67.50,28.50,48])))
"""
Bon #7 : 222 kr.
Bon #8 : 73 kr.
Bon #9 : 91 kr.
Bon #10 : 172 kr.
Bon #13 : 140 kr.
Bon #14 : 130 kr.
Bon #15 : 56.5 kr.
Bon #16 : 67.5 kr.
Bon #18 : 48 kr.
Total = 1000.0 kr.
"""
#[28.50, 48, 67.50, 56.50, 130, 140, 94, 73,74,73,64,156,79,24,16,78,39,12,73,73,49,83,73]
"""
Bon #7 : 73 kr.
Bon #8 : 74 kr.
Bon #9 : 73 kr.
Bon #10 : 64 kr.
Bon #11 : 156 kr.
Bon #12 : 79 kr.
Bon #13 : 24 kr.
Bon #14 : 16 kr.
Bon #15 : 78 kr.
Bon #17 : 12 kr.
Bon #18 : 73 kr.
Bon #19 : 73 kr.
Bon #20 : 49 kr.
Bon #21 : 83 kr.
Bon #22 : 73 kr.
Total = 1000 kr.
"""
tempSum = [None] * len(bons)
for ix,value  in enumerate(bons):
	tempSum[ix] = sum(bons[ix:])


target = 1000
count = 0
class BonCalculation:   
    def __init__(self, index, candidates, total):
        self.index = index
        self.candidates = candidates
        self.total = total
    
def run(bonCalc):
    #print(str(bonCalc.index) + " " +str(bonCalc.total))
    if (bonCalc.total >= target):
        return bonCalc
    if (bonCalc.index >= len(bons)):        
        return None
    global tempSum
    if (tempSum[bonCalc.index] + bonCalc.total < target):
    	return None
    global count
    count += 1
    newTotal = bonCalc.total + bons[bonCalc.index]
    newCandidates = bonCalc.candidates[:]
    newCandidates.append(bonCalc.index)
    withCalc =  BonCalculation(bonCalc.index+1,newCandidates,newTotal)
    withOutCalc =  BonCalculation(bonCalc.index+1,bonCalc.candidates[:],bonCalc.total)
    withRes = run(withCalc)
    withOutCalc = BonCalculation(bonCalc.index+1,bonCalc.candidates[:],bonCalc.total)
    withOutRes = run(withOutCalc)
   
    if(withRes==None):
        return withOutRes
    if(withOutRes==None):
        return withRes
    if(withRes.total < withOutRes.total):
        return withRes
    return withOutRes

allBons=sum(bons)

if (allBons<target):
    print ("Ingen kringle. Kun boner for : "+str(allBons))
else:
    result = run(BonCalculation(0,[],0))
    for candidate in result.candidates:
        print ("Bon #"+str(candidate) +" : " + str(bons[candidate]) + " kr.")
    print("Total = " + str(result.total) + " kr.")
    
print (count)