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

Question

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[i] = math.floor(temp_low/denom_new[i])
        temp_low = temp_low%denom_new[i]
        if (chip_count_low[i] == 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!

Answer 1

I have solved this problem by myself only. Just putting answer to close the thread.

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 min_chip_denom(amount, denominations):
  temp = []
  length = len(denominations)
  i = 0
  denominations.sort(reverse=True)
  chip_count = [0 for i in range(length)]
  while(i < length):
    chip_count[i] = math.floor(amount/denominations[i])
    amount = round(amount - chip_count[i]*denominations[i], 2)
    i = i + 1
  if (amount == 0):
    return chip_count
  else:
    return temp

def chip_denomination(amt_low, denominations):
  #denominations = [x for x in original_denominations if x <= amt_low]
  E = 1000
  temp_low = amt_low
  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)
      chip_count = min_chip_denom(amt_low, denom_new)
      if (len(chip_count) > 0):
        E_new = 4*N + 0.3*sum(chip_count)
        if (E_new < E):
          E = E_new
          final = [0 for i in range(len(denominations))]
          for j in range(N):
            final[elem_index(denom_new[j], denominations)] = chip_count[j]
    if (E - 4*(N+1) < 0):
      N = length
      print(f"Final -> Chips = {final}")
    else:
      N = N + 1

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