找到所有排列以获得给定的总和(硬币找零问题)

huangapple go评论74阅读模式
英文:

Finding all permutations to get the given sum (Coin change problem)

问题

我正在尝试解决一个经典的硬币找零问题(动态规划问题)。
为了使用动态规划方法找出无限面额硬币的所有唯一组合数以达到一个总和,我使用了以下方法:

/* 
     n - 硬币的数量
     arr[] - 硬币的面额
     x - 总和
     dp[] - 存储在索引i处的组合数的数组
*/
for (int j = 0; j < n; j++)
     for (int i = 1; i <= x; i++)
		  if (arr[j] <= i)
			  dp[i] = (long) ((dp[i] + dp[i - arr[j]]) % (1e9 + 7));

这给我提供了所有唯一可能的 组合 数量:

例如:

输入:
n=3 x=9
硬币面额:2 3 5

输出:
3

到目前为止,一切都很好。
但我观察到,只要交换上述代码片段中的循环顺序,我就会得到所有可能的 排列 数量:

for (int i = 1; i <= x; i++)
	for (int j = 0; j < n; j++)
		if (arr[j] <= i)
			dp[i] = (long) ((dp[i] + dp[i - arr[j]]) % (1e9 + 7));

这给我提供了所有唯一可能的 排列 数量:

例如:

输入:
3 9
2 3 5

输出:
8

通过调试并检查每次迭代,我发现了一个形成的模式,但不理解为什么会得到排列。有人能够迭代地解释给我吗?任何帮助都将不胜感激。

这两个问题可以在以下链接中找到:

英文:

I am trying to solve a classical coin-change (dynamic) problem.<br>
To find number of all unique combinations to get a sum from infinite denominations of coins using dynamic approach, i used this method:

/* 
     n - number of coins
     arr[] - coin denominations
     x - total sum
     dp[] - array to store number of combinations at index i.
*/
for (int j = 0; j &lt; n; j++)
     for (int i = 1; i &lt;= x; i++)
		  if (arr[j] &lt;= i)
			  dp[i] = (long) ((dp[i] + dp[i - arr[j]]) % (1e9 + 7));

This gives me all unique possible combinations count:<br>
Eg:

Input:
n=3 x=9
Coins: 2 3 5

Output:
3

So far ,all good.
But i observed that just by interchanging the loops in above snippet, i get all the possible permutations.<br>

for (int i = 1; i &lt;= x; i++)
	for (int j = 0; j &lt; n; j++)
		if (arr[j] &lt;= i)
			dp[i] = (long) ((dp[i] + dp[i - arr[j]]) % (1e9 + 7));

This gives me all unique possible permutations count:<br>
Eg:

Input:
3 9
2 3 5

Output:
8

With debugging and going through each iteration, i mapped a pattern that was formed, but didn't understand the reason behind why i am getting permutations.<br>
Can any one explain me this iteratively. Any help will be appreciated.<br>
Thanks

Both questions can be found here:<br>

答案1

得分: 3

第一段代码中,外部循环通过硬币更新在每轮外部循环的每一轮中以新硬币组成值的方式来更新 dp[] 中的组合数。因此,在第 k 轮之后,我们的 dp[] 数组将仅填充了使用前 k 个硬币的组合,而其余的硬币尚未被使用。如果我们为排序后的硬币数组存储组合本身,我们将只看到有序的组合,例如 1 1 5,而 5 永远不会在 1 之前出现。这就是为什么会出现这些组合的原因。

第二段代码在外部循环的第 m 轮中,使用所有可能的硬币来填充第 m 个单元格 dp[m]。因此,对于 m=7,我们会计算 1 1 51 5 15 1 1 这三种变种。这就是为什么会计算所有排列的原因。

此外,对于注释中提到的情况,我们可以创建一个二维数组,其中 dp[x][c] 包含以硬币 a[c] 结尾的总和为 x 的排列数。请注意,在这种情况下,我们必须将总和为 x-a[c] 的排列数的计数合并在一起。以下是相应的 1D 和 2D Python 代码:

def coins1(a, n):   # 排列数
    count = [1] + [0] * n
    for x in range(1, n + 1):
        for c in a:
            if (x - c >= 0):
                count[x] += count[x - c]
    return count[n]

def coins11(a, n):   # 排列数 2D
    m = len(a)
    count = [[1] + [0] * (m - 1)] + [[0] * m for i in range(n)]
    for x in range(1, n + 1):
        for c in range(m):
            if x >= a[c]:
                count[x][c] += sum(count[x - a[c]])
    return sum(count[n])

请注意,这些代码用于计算排列数,而不是组合数。

英文:

The first code with outer loop by coins updates number of ways to compose values dp[] with new coin at every round of outer loop. So after k-th round we have dp[] array filled with combinations of k coins only, and the rest of coins is not used yet. If we will store combinations themselves for sorted coin array, we will see only ordered ones like 1 1 5, and 5 never will go before 1. That is why combinations.

The second code at m-th round of outer loop fills m-th cell dp[m] using all possible coins. So we count for m=7 both 1 1 5 and 1 5 1 and 5 1 1 variants. That is why all permutations are counted here.


In addition for comment: we can make 2d array, where dp[x][c] contains number of permutations with sum x, ending with coin a[c]. Note that in this case we have to join counts of permutations with sum x-a[c]. For reference - 1d and 2d Python code.

def coins1(a, n):   #permutations
    count = [1]+[0]*n
    for x in range(1, n + 1):
        for c in a:
            if (x-c &gt;= 0):
                count[x] += count[x-c]
    return count[n]

def coins11(a, n):   #permutations 2d
    m = len(a)
    count = [[1] + [0]*(m-1)] + [[0]*m for i in range(n)]
    for x in range(1, n + 1):
        for c in range(m):
            if x&gt;=a[c]:
                count[x][c] += sum(count[x-a[c]])
    return sum(count[n])

huangapple
  • 本文由 发表于 2020年8月10日 03:04:25
  • 转载请务必保留本文链接:https://go.coder-hub.com/63330245.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定