动态编程硬币更改有限硬币

Question

动态编程找零题（限币）。我正在尝试创建一个作为 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.

输出：

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

并且输出应该是一个大小为 amount+1 的数组，其中每个单元格代表我们需要为单元格索引的数量找零的最佳硬币数量。

示例： 假设数组的单元格位于索引：5，内容为 2。这意味着为了找零 5(INDEX)，您需要 2(cell's content) 个硬币（最优解）。

基本上我需要这个 video(C[p]) 的第一个数组的输出 .这与 LIMITED COINS 的大 DIFFERENCE 完全相同的问题。 Link to Video.

注意：看视频就明白了，忽略视频的第二个数组，记住我不需要组合，而是DP数组，这样我就可以找到找零的硬币.

谢谢。

Answer 1

考虑下一个伪代码：

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

清楚了吗？

Answer 2

这就是您要找的。做出的假设：硬币价值按降序排列

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;
}

}

Answer 3

O(nk) 解决方案来自我前一段时间写的一篇社论：

我们从 O(k*sum(c)) 中运行的基本 DP 解决方案开始。我们有 dp 数组，其中 dp[i][j] 存储前 i 面额中总和为 j 的最少数量的硬币。我们有以下转换：dp[i][j] = min(dp[i - 1][j - cnt * value[i]] + cnt) for cnt from 0 to j / value[i].

为了将其优化为 O(nk) 解决方案，我们可以使用双端队列来记住上一次迭代的最小值并进行转换 O(1)。基本思想是，如果我们想在某个数组中找到最后 m 值的最小值，我们可以维护一个递增的双端队列来存储最小值的可能候选者。在每一步中，我们在将当前值推入后面的双端队列之前，弹出双端队列末尾大于当前值的值。由于当前值更靠右并且小于我们弹出的值，我们可以确定它们永远不会是最小值。然后，如果双端队列中的第一个元素超过 m 个元素，我们将其弹出。每一步的最小值现在只是双端队列中的第一个元素。

我们可以对这个问题应用类似的优化技巧。对于每个硬币类型 i，我们按以下顺序计算 dp 数组的元素：对于每个可能的 j % value[i] 值，我们按递增顺序处理 j 的值当除以 value[i] 时，该余数按递增顺序产生。现在我们可以应用双端队列优化技巧在常数时间内找到 min(dp[i - 1][j - cnt * value[i]] + cnt) for cnt from 0 to j / value[i]。

伪代码：

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()

Answer 4

你可以检查这个问题：。顺便说一句，我根据 link 的算法创建了 c++ 程序：

#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;
}

Answer 5

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

algorithm

dynamic-programming

coin-change