Dynamic Programming Coin Change Limited Coins

Question

Dynamic Programming Change Problem (Limited Coins). I'm trying to create a program that takes as INPUT:

int coinValues[]; //e.g [coin1,coin2,coin3]
int coinLimit[]; //e.g [2 coin1 available,1 coin2 available,...]
int amount; //the amount we want change for.

OUTPUT:

int DynProg[]; //of size amount+1.

And output should be an Array of size amount+1 of which each cell represents the optimal number of coins we need to give change for the amount of the cell's index.

EXAMPLE: Let's say that we have the cell of Array at index: 5 with a content of 2. This means that in order to give change for the amount of 5(INDEX), you need 2(cell's content) coins (Optimal Solution).

Basically I need exactly the output of the first array of this video(C[p]) . It's exactly the same problem with the big DIFFERENCE of LIMITED COINS. Link to Video.

Note: See the video to understand, ignore the 2nd array of the video, and have in mind that I don't need the combinations, but the DP array, so then I can find which coins to give as change.

Thank you.

The video explains this problem with unlimited coins. I want an implementation with limited coins. I cant find this version anywhere, all algorithms are wrong or have as output the number of combinations. — DIMITRIOS, May 24 '17 at 13:18
You are asking how to get value x with the smallest amount of coins? — maraca, May 24 '17 at 14:34
There are numerous similar questions on Stack Overflow like https://stackoverflow.com/questions/4198210/coin-change-with-limited-number-of-coins and https://stackoverflow.com/questions/28910971/dynamic-programming-coin-change-problems. In fact, I got 343 hits on Stack Overflow when I searched Google with your question title. Did none of these questions help you? — beaker, May 24 '17 at 14:36
@beaker : the 1st question as i said is only about the combinations. The 2nd is about ulimited coins. I cant find the right implemantation. — DIMITRIOS, May 24 '17 at 14:41
I don't think you can use this dp technique because with unlimited coins you can add any coin to any combination but with limited amounts you can only add certain coins to certain combinations. You could probably sort the coins descending and then use standard backtracking and cut all branches with more coins than shortest solution found so far. — maraca, May 24 '17 at 14:58

score 1 · Accepted Answer · answered May 24 '17 at 15:39

Consider the next pseudocode:

for every coin nominal v = coinValues[i]:
    loop coinLimit[i] times:
        starting with k=0 entry, check for non-zero C[k]:
            if C[k]+1 < C[k+v] then
                  replace C[k+v] with C[k]+1 and set S[k+v]=v

Is it clear?

score 1 · Answer 2 · answered Aug 17 '18 at 22:44

O(nk) solution from an editorial I wrote a while ago:

We start with the basic DP solution that runs in O(k*sum(c)). We have our dp array, where dp[i][j] stores the least possible number of coins from the first i denominations that sum to j. We have the following transition: dp[i][j] = min(dp[i - 1][j - cnt * value[i]] + cnt) for cnt from 0 to j / value[i].

To optimize this to an O(nk) solution, we can use a deque to memorize the minimum values from the previous iteration and make the transitions O(1). The basic idea is that if we want to find the minimum of the last m values in some array, we can maintain an increasing deque that stores possible candidates for the minimum. At each step, we pop off values at the end of the deque greater than the current value before pushing the current value into the back deque. Since the current value is both further to the right and less than the values we popped off, we can be sure they will never be the minimum. Then, we pop off the first element in the deque if it is more than m elements away. The minimum value at each step is now simply the first element in the deque.

We can apply a similar optimization trick to this problem. For each coin type i, we compute the elements of the dp array in this order: For each possible value of j % value[i] in increasing order, we process the values of j which when divided by value[i] produces that remainder in increasing order. Now we can apply the deque optimization trick to find min(dp[i - 1][j - cnt * value[i]] + cnt) for cnt from 0 to j / value[i] in constant time.

Pseudocode:

let n = number of coin denominations
let k = amount of change needed
let v[i] = value of the ith denomination, 1 indexed
let c[i] = maximum number of coins of the ith denomination, 1 indexed
let dp[i][j] = the fewest number of coins needed to sum to j using the first i coin denominations

for i from 1 to k:
    dp[0][i] = INF

for i from 1 to n:
    for rem from 0 to v[i] - 1:
        let d = empty double-ended-queue
        for j from 0 to (k - rem) / v[i]:
            let currval = rem + v[i] * j
            if dp[i - 1][currval] is not INF:
                while d is not empty and dp[i - 1][d.back() * v[i] + rem] + j - d.back() >= dp[i - 1][currval]:
                    d.pop_back()
                d.push_back(j)
            if d is not empty and j - d.front() > c[i]:
                d.pop_front()
            if d is empty:
                dp[i][currval] = INF
            else:
                dp[i][currval] = dp[i - 1][d.front() * v[i] + rem] + j - d.front()

score 0 · Answer 3 · answered Aug 17 '18 at 04:00

This is what you are looking for. Assumptions made : Coin Values are in descending order

public class CoinChangeLimitedCoins {

public static void main(String[] args) {
    int[] coins = { 5, 3, 2, 1 };
    int[] counts = { 2, 1, 2, 1 };
    int target = 9;
    int[] nums = combine(coins, counts);
    System.out.println(minCount(nums, target, 0, 0, 0));
}

private static int minCount(int[] nums, int target, int sum, int current, int count){
    if(current > nums.length) return -1;
    if(sum == target) return count;
    if(sum + nums[current] <= target){
        return minCount(nums, target, sum+nums[current], current+1, count+1);
    } else {
        return minCount(nums, target, sum, current+1, count);
    }
}

private static int[] combine(int[] coins, int[] counts) {
    int sum = 0;
    for (int count : counts) {
        sum += count;
    }
    int[] returnArray = new int[sum];
    int returnArrayIndex = 0;
    for (int i = 0; i < coins.length; i++) {
        int count = counts[i];
        while (count != 0) {
            returnArray[returnArrayIndex] = coins[i];
            returnArrayIndex++;
            count--;
        }
    }
    return returnArray;
}

}

Nope. Your code wouldn't work for change = 600 and nominalas { 20x 500, 20x 200, 700x 1}. Your alghoritm will return 1x500 and 100x 1. — Bartek Chyży, Mar 12 '19 at 22:51

score 0 · Answer 4 · answered Jan 21 '21 at 05:06

You can check this question: Minimum coin change problem with limited amount of coins. BTW, I created c++ program based above link's algorithm:

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
void copyVec(vector<int> from, vector<int> &to){
    for(vector<int>::size_type i = 0; i < from.size(); i++)
        to[i] = from[i];
}
 vector<int> makeChangeWithLimited(int amount, vector<int> coins, vector<int> limits)
        {
            vector<int> change;
            vector<vector<int>> coinsUsed( amount + 1 , vector<int>(coins.size()));
            vector<int> minCoins(amount+1,numeric_limits<int>::max() - 1);
            minCoins[0] = 0;
            vector<int> limitsCopy(limits.size());
            copy(limits.begin(), limits.end(), limitsCopy.begin());

        for (vector<int>::size_type i = 0; i < coins.size(); ++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;
                            copyVec(coinsUsed[j], coinsUsed[currAmount]);
                            coinsUsed[currAmount][i] += 1;
                        }
                    }
                }

                limitsCopy[i] -= 1;
            }
        }

        if (minCoins[amount] == numeric_limits<int>::max() - 1)
        {
            return change;
        }

        copy(coinsUsed[amount].begin(),coinsUsed[amount].end(), back_inserter(change) );
        return change;
    }

int main()
{
    vector<int> coins;
    coins.push_back(20);
    coins.push_back(50);
    coins.push_back(100);
    coins.push_back(200);
    vector<int> limits;
    limits.push_back(100);
    limits.push_back(100);
    limits.push_back(50);
    limits.push_back(20);
    int amount = 0;
    cin >> amount;
    while(amount){
    vector<int> change = makeChangeWithLimited(amount,coins,limits);
    for(vector<int>::size_type i = 0; i < change.size(); i++){
        cout << change[i] << "x" << coins[i] << endl;
    }
    if(change.empty()){
        cout << "IMPOSSIBE\n";
    }
    cin >> amount;
    }
    system("pause");
    return 0;
}

score 0 · Answer 5 · answered Jul 23 '21 at 07:42

Code in c#

private static int MinCoinsChangeWithLimitedCoins(int[] coins, int[] counts, int sum)
    {
        var dp = new int[sum + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;

        for (int i = 0; i < coins.Length; i++) // n
        {
            int coin = coins[i];
            for (int j = 0; j < counts[i]; j++) // 
            {
                for (int s = sum; s >= coin ; s--) // sum
                {
                    int remainder = s - coin;
                    if (remainder >= 0 && dp[remainder] != int.MaxValue)
                    {
                        dp[s] = Math.Min(1 + dp[remainder], dp[s]);
                    }
                }
            }

        }
        
        return dp[sum] == int.MaxValue ? -1 : dp[sum];
    }

Dynamic Programming Coin Change Limited Coins

5 Answers5

Linked