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

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.

输出应该是大小为1的数组，其中每个单元格代表我们需要改变单元格索引量的最佳硬币数。

假设数组的单元格位于index： 5，内容为2。这意味着为了给出5（INDEX）的变化，您需要2（单元格的内容）硬币（最佳解决方案）。

基本上，我需要这个视频的第一个数组的输出（C[p]）。这与有限硬币的大区别是完全相同的问题。链接到视频。

注意：看到视频了解，忽略视频的第2个数组，并记住我不需要组合，但DP数组，这样我就可以找到哪些硬币作为零钱。

非常感谢。

Answer 1

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

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 2

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）从0到j/value[i]。

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

我们可以将类似的优化技巧应用于这个问题。对于每个硬币类型i，我们按此顺序计算dp数组的元素：对于每个可能的值j%value[i]，我们按递增顺序处理j的值当除以value[i]时，会产生递增顺序的余数。现在，我们可以应用deque优化技巧，在恒定时间内从0到j/value[i]查找cnt的min（dp[i-1][j-cnt*value[i]]cnt）。

伪代码：

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 3

考虑下一个伪代码：

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

清楚了吗？