动态编程，用于代币兑换 [英] Dynamic Programming for a variant of the coin exchange

问题描述

我有兴趣解决硬币兑换问题的一个变体。回想一下硬币交换问题的正式定义：

I am interested in solving a variant of the coin exchange problem. Recall the formal definition of the coin exchange problem:

给定值 N ，如果我们想更改 N 分，并且我们有无限数量的 S = {S1，S2，..，Sm} 整数值硬币，我们可以用几种方法进行更改？硬币的顺序无关紧要。例如，对于 N = 4和 S = {1,2,3} ，有四个解：{1,1,1,1}，{1， 1,2}，{2,2}，{1,3}。因此输出应为4。对于 N = 10和 S = {2，5，3，6} ，有五个解：{2,2,2,2 ，2}，{2,2,3,3}，{2,2,6}，{2,3,5}和{5,5}。因此输出应为5。请参见此处

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = {S1, S2, .. , Sm} integral-valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5. See here for further detail.

在这里，您可以找到针对此问题的基于列表DP的解决方案。此解决方案基于以下递归关系：

Here, one can find a tabulation-DP-based solution for this problem. This solution is based on the following recurrence relation:

count(S, m, n) = count(S, m - 1, n) + count(S, m, n - S[m - 1]);

有基本情况：

count(S, m, n < 0) = 0
count(S, m, n = 0) = 1
count(S, m <= 0, n >= 1) = 0

直觉上，此递归关系将问题定义为两个问题的解决方案子问题：那些我们丢弃硬币的地方，以及那些我们假设硬币一次被逐步使用的地方。

Intuitively, this recurrence relation defines a problem as the solution to two sub-problems: Those in where we discard coins, and those for which we assume the coins a progressively used once at the time.

问题 ：如何修改此递归关系以计算我们可以求和到 N 而不考虑顺序和加偶数个数的方式？例如，对于 N = 4和 S = {1,2,3} ，总共有四个解（不考虑顺序）：{1,1,1,1 }，{1,1,2}，{2,2}，{1,3}，但其中只有3个具有偶数个被加数，即{1,1,1,1}，{2,2} ，{1,3}。

Question: How can I modify this recurrence relation to count the number of ways we can sum to N disregarding order and with an even number of summands? For example, for N = 4 and S = {1,2,3}, there are four solutions total (disregarding order): {1,1,1,1},{1,1,2},{2,2},{1,3}, but only 3 of them have an even number of summands, i.e. {1,1,1,1},{2,2},{1,3}.

先前的研究：起初，我认为在丢弃硬币的情况下，我可以将请求的金额加倍，并且要求在使用某些硬币的情况下每个硬币被消耗两次，即：

Previous research: At first I thought I could double the requested sum for the case of discarding coins, and requesting that each coin is consumed twice for the cases in where we would use some of the coins, i.e.:

count(S, m, n) = count(S, m - 1, 2*n) + count(S, m, n - 2*S[m - 1]);

此功能适用于某些示例案例，但无效。有什么提示吗？

This works for some sample cases, but it does not work. Any hints?

推荐答案

您需要在递归中添加一个标志，该标志是到目前为止使用的求和数的奇偶校验。

You need to add a flag to the recursion which is the parity of the number of summands used so far.

使用加法运算时，请翻转标志（ S（nv [m]，m，！parity））。

When using a summand you flip the flag (S(n-v[m],m,!parity)).

基本情况为：

n=0 parity=0 -> 1

n=0 parity=1 -> 0

n<0 or m<0 (array is 0-indexed) -> 0

以下是c ++中的递归函数。当然，您需要记住它，以便它可以使用更大的值。

Below is the recursive function in c++. Ofcourse you need to memoize it for it to work on bigger values.

int S(int n,int m,bool parity)
{
    if (n==0)
    {
        if (parity==1)
            return 0;
        else 
            return 1;
    }
    if (m<0 || n<0)
        return 0;
    return S(n,m-1,parity)+S(n-v[m],m,!parity);
}

这篇关于动态编程，用于代币兑换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！