Minimum coin change problem with limited amount of coins

Question

To be specific, the problem is:
Given array of denominations coins[], array of limit for each coins limits[] and number amount, return minimum number of coins needed, to get the amount, or if it's not possible return null. Additionally fill array change with number of each coin used in the solution.

This is my solution:

public static int? Dynamic(int amount, int[] coins, int[] limits, out int[] change)
{
    int[] minCoins = new int[amount + 1];
    int[,] coinsUsedToAmount = new int[coins.Length, amount + 1];

    minCoins[0] = 1;
    for (int j = 0; j < amount; ++j)
    {
        if (minCoins[j] == 0)
        {
            continue;
        }
        
        for (int i = 0; i < coins.Length; ++i)
        {
            if (coinsUsedToAmount[i, j] >= limits[i])
            {
                continue;
            }
            
            int currAmount = j + coins[i];
            if (currAmount <= amount 
                && (minCoins[currAmount] == 0 
                    || minCoins[currAmount] > minCoins[j] + 1))
            {
                minCoins[currAmount] = minCoins[j] + 1;
                for (int k = 0; k < coins.Length; ++k) 
                {
                    coinsUsedToAmount[k, currAmount] = coinsUsedToAmount[k, j];
                }
                coinsUsedToAmount[i, currAmount] += 1;
            }
        }
    }

    if (minCoins[amount] == 0)
    {
        change = null;
        return null;
    }

    change = new int[coins.Length];
    for(int i = 0; i < coins.Length; ++i)
    {
        change[i] = coinsUsedToAmount[i, amount];
    }

    return minCoins[amount] - 1;
}

But it doesn't work in general.

My issue is that for example in such case:

amount = 141, 
coins = new int[] { 2, 137, 65, 35, 30, 9, 123, 81, 71 }                                                                                  
limits = new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1 }

Optimal solution is:

 change = new int[] { 1, 0, 1, 1, 1, 1, 0, 0, 0 }

And my algorithm gives null as the result. In the other words it fails, whenever on some way up I would have to use less optimal solution than it's possible, and then, at the end, I don't have necessary coins.

So, in this example my algorithm makes a mistake in following step:

minCoins[132] = (9 + 123) // 2 coins

But it should be:

minCoins[132] = (2 + 65 + 35 + 30) // 4 coins

because then I can use 9 and have 141.

I have been coming back to this problem for a few weeks now and I still can't solve it. I had seen numerous solutions to similar problems on this and other sites, but none of them helped me.

Hexamerous

Answer 1

Friend of mine helped me solve it. The idea is that we go from the amount to 0 and try to use all the nominal of each coins possible - that way we won't end up using certain coins at the beginning, and then we wouldn't have possibility to use them for amount.

/// <summary>
///  Method used to resolve minimum change coin problem
///  with constraints on the number of coins of each type.
/// </summary>
/// <param name="amount">Amount of change to make, e.g. 13</param>
/// <param name="coins">Available types of coins, e.g. {1, 2, 3, 5}</param>
/// <param name="limits">Number of available coins of specific type, e.g. {1, 5, 3, 2}</param>
/// <param name="change">Number of coins of each type used to make the change, e.g. {0, 0, 1, 2}</param>
/// <returns>
///  Minimal number of coins needed to make the change 
///  (equal to sum of change array entries), e.g. 3
/// </returns>
/// <remarks>
///  coins[i]  - nominal value of the coin of i-th type
///  limits[i] - number of available coins of i-th type (denomination)
///  change[i] - number of coins of i-th type used in the solution
/// 
///  If available `coins` and `limits` does not allow to make provided `amount` of change 
///  then `change` should be set to `null`, and method should also return `null`.
///
///  Tips/requirements:
///   The size of work memory of the algorithm should (must) be 
///   proportional to the value of product: `amount*(coins.Length)` 
///   (that is O(amount*(coins.Length))
/// </remarks>
public static int? Dynamic(int amount, int[] coins, int[] limits, out int[] change)
{
        int[][] coinsUsed = new int[amount + 1][];
        for (int i = 0; i <= amount; ++i)
        {
            coinsUsed[i] = new int[coins.Length];
        }

        int[] minCoins = new int[amount + 1];
        for (int i = 1; i <= amount; ++i)
        {
            minCoins[i] = int.MaxValue - 1;
        }

        int[] limitsCopy = new int[limits.Length];
        limits.CopyTo(limitsCopy, 0);

        for (int i = 0; i < coins.Length; ++i)
        {
            while (limitsCopy[i] > 0)
            {
                for (int j = amount; j >= 0; --j)
                {
                    int currAmount = j + coins[i];
                    if (currAmount <= amount)
                    {
                        if (minCoins[currAmount] > minCoins[j] + 1)
                        {
                            minCoins[currAmount] = minCoins[j] + 1;

                            coinsUsed[j].CopyTo(coinsUsed[currAmount], 0);
                            coinsUsed[currAmount][i] += 1;
                        }
                    }
                }

                limitsCopy[i] -= 1;
            }
        }

        if (minCoins[amount] == int.MaxValue - 1)
        {
            change = null;
            return null;
        }

        change = coinsUsed[amount];
        return minCoins[amount];
}

Hexamerous

Is this example working? I checked and couldn't get answer. – Octagonal

@HimashiRodrigo, yes it should work - I've just checked (on the provided example). I also added some documentation if it helps. – Hexamerous