动态规划 零钱兑换 有限硬币

Question

动态规划找零问题（有限硬币）。 我正在尝试创建一个程序，它的输入：

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)个硬币（最佳解决方案）。

基本上，我需要完全与此视频(C[p])的第一个数组相同的输出。它与大的DIFFERENCE的问题完全相同。LIMITED COINS。 视频链接。

注意：观看视频以理解，忽略视频的第二个数组，并记住我不需要组合，而是DP数组，然后我可以找到要作为找零的硬币。

谢谢。

- DIMITRIOS

---

你对算法实现有什么问题吗？ - MBo

这个视频解释了无限硬币的问题，但我需要一个有限硬币的实现。我找不到这个版本，所有的算法都是错误的或者输出组合数量。 - DIMITRIOS

在 Stack Overflow 上有许多类似的问题，例如 https://dev59.com/NVHTa4cB1Zd3GeqPV_Be 和 https://dev59.com/bl4b5IYBdhLWcg3wnCty。事实上，当我使用您的问题标题在 Google 上搜索时，在 Stack Overflow 上找到了 343 个相关结果。这些问题都没有对您有所帮助吗？ - beaker

@beaker：第一个问题就像我说的只涉及组合。第二个问题是关于无限硬币的，我找不到正确的实现方法。 - DIMITRIOS

我认为你不能使用这种动态规划技术，因为有无限的硬币可以将任何硬币添加到任何组合中，但是有限数量的硬币只能将某些硬币添加到某些组合中。你可以将硬币按降序排序，然后使用标准回溯法，并剪枝所有比迄今为止找到的最短解决方案更多的分支。 - maraca

Answer 1

O(nk)解法来自我之前写的一篇文章：

我们从基本的DP解法开始，它的时间复杂度为O(k*sum(c))。我们有一个dp数组，其中dp[i][j]存储了前i个面值中总和为j所需的最少硬币数。我们有以下转移方程：dp[i][j] = min(dp[i - 1][j - cnt * value[i]] + cnt)，其中cnt从0到j / value[i]。

为了将其优化为一个O(nk)的解决方案，我们可以使用双端队列来记忆前一次迭代中的最小值，并使过渡变得O(1)。基本思想是，如果我们想要在某个数组中找到最后m个值的最小值，我们可以维护一个递增的双端队列，存储可能成为最小值的候选项。每一步，我们弹出队列末尾大于当前值的值，然后将当前值推入队列的末尾。由于当前值既向右更远又小于我们弹出的值，我们可以确定它们永远不会是最小值。然后，如果第一个元素比m个元素远，我们就弹出队列中的第一个元素。每一步的最小值现在就是队列中的第一个元素。

我们可以对这个问题应用类似的优化技巧。对于每种硬币类型 i ，我们按照以下顺序计算dp数组的元素：对于递增的每个可能的值j％value[i]，我们按照被value[i]除后产生该余数的j值的递增顺序处理。现在，我们可以应用deque优化技巧，在常数时间内找到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()

- eesiraed

Answer 2

考虑下面的伪代码：

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

它清楚吗？

- MBo

Answer 3

这就是你要找的内容。 假设：硬币价值按降序排列。

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

}

- Nishit

---

不行。你的代码对于change = 600和nominalas {20x 500，20x 200，700x 1}是无效的。你的算法将返回1x500和100x 1。 - Bartek Chyży

Answer 4

你可以查看这个问题：有限硬币找零问题。 顺便说一下，我基于上面链接的算法创建了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;
}

- Sharofiddin

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

- Pradeep Tiwari