Finding Optimal Change for Lowest Coin Total

Question

So this is a two-part problem involving coins. The first part involves summing the coin counts of amounts 1-99 cents (for example, it takes 1 coin to get to 1 cent, 2 coins to get to 2 cents, etc. and adding the total amount of coins it takes to get to each value). This can be represented by the following code (feel free to make suggestions/improvements):

def findbest(origarray, denom):
    current = origarray
    i = 1
    while(i < size):
        if(i in denom):
            current[i] = 1
            coinlist[i] = [i]
        else:
            k = 1
            while(k < 1 + (i/2)):
                c = current[k] + current[i-k]
                if(c < current[i]):
                    current[i] = c
                    coinlist[i] = coinlist[k] + coinlist[i-k]
                k+=1
        print i, current[i], coinlist[i]
        i+=1
    return current


size = 100
coinlist = [[]]
origarray = [0] 
i = 1

while(i < size):
    origarray.append(100)
    coinlist.append([])
    i += 1

denom = [1,5,10,25,50]

x = findbest(origarray, denom)

total=0

for value in findbest(origarray,denom):
    total += value

print total


print "\n\n\n"
print x

The second part of the problem is finding the ideal three denominations (don't have to be real denominations, but one has to be 1) that will yield the lowest total of all coin counts. This is where it gets tricky for me. I know I have to write something that will brute-force the denomination values until it finds the optimal three (which I know are [1,12,19], I just can't get to that point), but I'm not sure how to go about doing that. Does anyone have an idea of how to do this?

Answer 1

The function you're looking for, that will make this completely trivial is itertools.combinations.

>>> from itertools import combinations
>>> len(list(a for a in combinations(range(1, 101), 3)))
161700

I'd suggest an implementation based off of yours as something like this:

def findbest(origarray, denom):
    current = origarray
    i = 1
    while(i < size):
        if(i in denom):
            current[i] = 1
            coinlist[i] = [i]
        else:
            k = 1
            while(k < 1 + (i/2)):
                c = current[k] + current[i-k]
                if(c < current[i]):
                    current[i] = c
                    coinlist[i] = coinlist[k] + coinlist[i-k]
                k+=1
        #print i, current[i], coinlist[i]
        i+=1
    return current

size = 100

def reset_cache():
  i = 1
  global coinlist
  coinlist = [[]]
  global origarray
  origarray = [0] 

  while(i < size):
      origarray.append(100)
      coinlist.append([])
      i += 1

reset_cache()

denom = [1,5,10,25,50]

x = findbest(origarray, denom)

total=0

for value in findbest(origarray,denom):
    total += value

print total


print "\n\n\n"
print x


from itertools import combinations

best = ((0,0,0), 1e6)
for comb in combinations(range(1, 101), 3):
  #print "Considering: %s" % comb
  reset_cache()
  total = 0
  for value in findbest(origarray, comb):
    total += value
  if total < best[1]:
    print "%s beat best with %d" % (comb, total)
    best = (comb, total)

print best

But I am bothered by needing what I suppose is a coin cache? I'm not sure, I didn't read your code too hard. But I don't like the necessity of passing in a few arrays to make it work. It should be self-contained.

EDIT: Seems to me that you can actually get away

for comb in [(1,) + a for a in combinations(range(2, 101), 2)]:

because any valid change system will need to have a 1 cent coin. This makes the code run much faster because

>>> len([(1,) + a for a in combinations(range(2, 101), 2)])
4851

Answer 2

my java version

public static int minChange(int[] coins, int total) {
        int[] counts = new int[total + 1];
        counts[0] = 0;
        int MAX = Integer.MAX_VALUE - 1;
        for (int i = 1; i <= total; ++i) {
            int count = MAX;
            for (int j = 0; j < coins.length; ++j) {
                if (i - coins[j] >= 0 && count > counts[i - coins[j]])
                    count = counts[i - coins[j]];
            }
            if (count < MAX)
                counts[i] = count + 1;
            else
                counts[i] = MAX;
        }
        return counts[total];
    }