[Python] Find the combination of coin chips by minimising the value of E=4N + 0.3n

I want to find the perfect combination of coin chips for an amount (say A) for given denominations = [0.1, 0.5, 1, 5, 20, 100, 500].

There are multiple combinations possible but we have to consider only that combination list which will have minimum value of

E = 4N + 0.3n
​

where

N -> Total no. of different types of chips
n -> Total count of all the chips.


For example -:

Let's suppose amount A = 6.8, then acceptable combination would be [8, 0, 6, 0, 0, 0, 0] with E = 4 * 2 + 0.3 * 14 = 12.2 (N = 2 and n = 8 + 6 = 14)

My Try -:

I am not really good at coding, so my code is not giving the correct answer.

from itertools import permutations
from itertools import combinations
import math

def elem_index(elem, arr):
try:
index = arr.index(elem)
except ValueError:
index = -1
return index

def comb(arr, pos):
comb_temp = combinations(arr, pos)
result = [list(p) for p in comb_temp]
return result

def chip_denomination(amt_low, denominations):
#denominations = [x for x in original_denominations if x <= amt_low]
E = 1000
temp_low = amt_low
final = [0 for i in range(len(denominations))]
length = len(denominations)
N = 1
while (N < length):
comb_arr = comb(denominations, N)
chip_count_low = [0 for i in range(N)]
for denom_new in comb_arr:
denom_new.sort(reverse=True)
i = 0
while (i < N):
chip_count_low = math.floor(temp_low/denom_new)
temp_low = temp_low%denom_new
if (chip_count_low == 0 or (i == N-1 and temp_low > 0)):
i = N
else:
i = i + 1
if (elem_index(0, chip_count_low) == -1):
E_new = 4*N + 0.3*sum(chip_count_low)
if (E_new < E):
E = E_new
for j in range(N):
final[elem_index(denom_new[j], denominations)] = chip_count_low[j]
if (E - 4*(N+1) < 0):
N = length
else:
print(f"Chips = {final} and Effort = {E} and N={N}")
N = N + 1

denominations = [0.1, 0.5, 1, 5, 20, 100, 500]
amt_low = 6.8
chip_denomination(amt_low, denominations)


Would really appreciate if someone can help me to write the correct code. Thanks!

Continue reading...