A variant of coin change problem

Question

Consider a cashier machine that takes payments in coins. We feed the machine coins one by one until the value is more than the amount we should have paid. Then the machine returns the extra amount in coins in the least number of coins possible. So we have k type of coins and a limited amount of each type. Also the machine has an unlimited amount of each of the k types of coins so it can return us the exact amount it should (there is always coin with value 1). So we want to minimize the number of coins we have after we have paid for the items we have bought. Consider this example: We have 3 kinds of coins of values 1, 2 and 4 and we have to pay 15 dollars. We have 10 coins with value 1, 7 coins with value 4 and 5 coins with value 2. There are multiple ways to minimize our coins after the process. One of them is to give the machine 10 coins with value 1 and 3 coins with value 2. Thus we have paid 16 dollars with 13 coins and the machine should return to us 1 dollar and it returns us 1 coin with value 1. So we have spent 12 coins. The other way is to give the machine 9 coins with value 1 and 3 coins with value 2 and the machine doesn't return us anything. So we have paid 12 coins.

My approach to the problem is to divide the problem to two separate coin change problem. The easier problem is when the machine returns us the extra amount of money we have paid. I think this is a simple coin change problem that we want to change some amount of money to the minimum number of coins. The main problem is to pay the machine some maximal amount of coin with the restrictions mentioned above. The restrictions were that we have limited number of each coin and if want to pay A dollars the machine stops receiving coins when the amount of money we have paid becomes equal or greater than A. So For example if we have to pay to 15 dollars and we want to use a total amount of 18 dollars to pay we should use at least a coin with value 4 (18-15+1) or else at some point in the process of paying the amount we have given to the machine surpasses 15 and it won't receive any more coins.

So what I have done so far is this

A //amount we should pay
D //value of the coin with max value among all present coin types
for value_to_change in A to A+D-1
   clear the memoized table for maximal_change
   r = maximal_change(value_to_change,0,0)
   d = minimal_change(value_to_change-A)
   ans = max( ans, r-d ) 

max_coin // the maximum value of the coin we have used so far
maximal_change( value_to_change, index_of_coin_type, max_coin )
   if we have computed (value_to_change, index_of_coin_type)
       return the computed value
   if (it is the last coin type) AND (max_coin > A-value_to_change) 
       if value_to_change % value[index_of_coin_type]==0
            return value_to_change / value[index_of_coin_type]
       else
            return we cant change this value with this coin // -1
   for i in [0, number_of_available_coins_with_this_type]
       n = maximal_change( value_to_change - i*value_of_this_coin_type, 
                           index_of_coin_type+1, 
                           max(max_coin, value_of_this_coin_type) )
       if n != -1 // we can change the value
           result = max(n+i, result)      
   dp[value_to_change][index_of_coin_type] = result;
   return result

now my problem is my solution is slower than what is expected and I think it is because that I clear the memoized table for every value to change. This is only because in each value to change we are required to use a coin with value at least (value_to_change-A+1). Anybody has a better solution?

link of the full description of the problem
link of my implementation

Answer 1

I agree with your solution of the isolated case. Your problem is to reuse your memoisation table. Suppose there are n cases.

What I imagine you could do is:

Allocate a matrix to hold all cases. It has dimensions: T, 1 <= coin value = 50. Call the maximum coin value C. The maximum number of coins is 1000. You could store each count in an unsigned 16 bit int. This max total memory so far of 100 * 50 * 16 = 80KB. We're given 65536, so this isn't too bad. Call this M1.

You now want to devise a plan to reuse your memoisation table as much as possible. As far as I can see, you can reuse a table if and only if the multi-set of coins of the next case is a superset of the previous.

You need to find a way of partitioning the rows into M1 into sequences where each successive vector represents a superset of the previous. That is, the values of coin counts should be non-decreasing over successive vectors.

What you would like to do is minimise the number of partitions. Given two plans with the same number of partitions, you would choose the one which minimises the maximum number of differing coins for a given partition, which would in turn make the solution of the isolated cases cheaper.

I'm not completely sure about the complexity of this, although I imagine that it is NP-Hard, given the number of possible partitions and its similarity to the partition problem. It seems like there might be a cheap randomised greedy algorithm to find a set of initial sequences and work from there.

To run the plan, iterate over the sequences, initialising the memoisation table each time. Run the first case as normal. Run the second case by computing change combinations only for the set of new larger combinations of each coin.