多种代币兑换的动态编程解决方案

编程入门 行业动态 更新时间:2024-10-08 04:25:18
本文介绍了多种代币兑换的动态编程解决方案的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧! 问题描述

我正在练习动态编程。我关注的是硬币兑换问题的以下变体:

I am practicing Dynamic Programming. I am focusing on the following variant of the coin exchange problem:

让 S = [1,2,6,12,24,48, 60] 是一组固定的整数硬币面额。假设 n 是通过 S 中的硬币可获得的正整数金额。考虑两个人 A 和 B 。我可以通过多种方式将 n 分配给 A 和 B ,以便每个人都能获得相同数量的硬币(不考虑每个人实际获得的货币数量)?

Let S = [1, 2, 6, 12, 24, 48, 60] be a constant set of integer coin denominations. Let n be a positive integer amount of money attainable via coins in S. Consider two persons A and B. In how many different ways can I split n among persons A and B so that each person gets the same amount of coins (disregarding the actual amount of money each gets)?

示例

n = 6 每人可以分为4种不同的方式:

n = 6 can be split into 4 different ways per person:

  • 人员 A 得到{2,2},个人 B 得到{1 ,1}。
  • 人员 A 获得{2,1},个人 B 得到{2,1}。
  • 人 A 得到{1,1}和人 B 得到{2,2}。
  • 人 A 得到{1,1,1}和一个人 B 得到{1,1,1}。
  • Person A gets {2, 2} and person B gets {1, 1}.
  • Person A gets {2, 1} and person B gets {2, 1}.
  • Person A gets {1, 1} and person B gets {2, 2}.
  • Person A gets {1, 1, 1} and person B gets {1, 1, 1}.
  • 请注意每种方式是每人非冗余的,即我们不将{2,1}和{1,2}都视为两种不同方式。

    Notice that each way is non-redundant per person, i.e. we do not count both {2, 1} and {1, 2} as two different ways.

    先前的研究

    我研究了非常相似的DP问题,例如硬币交换问题和分区问题。实际上,此站点中存在与几乎相同的问题有关的问题:

    I have studied at very similar DP problems, such as the coin exchange problem and the partition problem. In fact, there are questions in this site referring to almost the same problem:

    • 动态编程,用于代币兑换-在这里,OP研究递归关系,但引入时似乎有些困惑
    • 硬币更改:动态编程 -在这里,OP似乎正在寻求解决方案的重建。
    • 硬币更改(动态编程)-在这里,OP似乎也在寻求解决方案的重构。
    • cs.stackexchange/questions/87230/用于多种变量的动态编程he-coin-exchange-problem -在这里,OP似乎在问一个类似的问题,但平价即分成两个人成为主要问题。
    • Dynamic Programming for a variant of the coin exchange - Here, OP studies the recursion relationship, but seems confused introducing the parity constraint.
    • Coin Change :Dynamic Programming - Here, OP seems to pursue the reconstruction of the solution.
    • Coin change(Dynamic programming) - Here, OP seems to also pursue the reconstruction of the solution.
    • cs.stackexchange/questions/87230/dynamic-programming-for-a-variant-of-the-coin-exchange-problem - Here, OP seems to ask about a similar problem, yet parity, i.e. splitting into two persons, becomes the main issue.

    我主要对可以帮助我解决此问题的递归关系感兴趣。定义它将使我能够轻松地采用制表法的记忆来设计此问题的算法。

    I am interested mostly in the recursion relation that could help me solve this problem. Defining it will allow me to easily apply either a memoization of a tabulation approach to design an algorithm for this problem.

    例如,此递归:

    def f(n, coins): if n < 0: return 0 if n == 0: return 1 return sum([f(n - coin, coins) for coin in coins])

    虽然很诱人,但却无法正常工作,因为执行时:

    Is tempting, yet it does not work, because when executed:

    # => f(6, [1, 2, 6]) # 14

    以下是一个运行示例 S'= {1,2,6} 和 n = 6 ,是为了帮助我阐明模式(可能有错误):

    Here's an example of a run for S' = {1, 2, 6} and n = 6, in order to help me clarify the pattern (there might be errors):

    推荐答案

    这是您可以尝试的方法:

    This is what you can try:

    让 C (n,k,S)是使用某些 k 个硬币。

    Let C(n, k, S) be the number of distinct representations of an amount n using some k coins from S.

    然后 C(n,k,S) = sum(C(n-s_i,k-1,S [i:]))求和是针对<$ c中的每个 s_i $ c> S 。 S [i:] 表示 S 中所有元素均从 i -th元素到最后-我们需要它来防止重复组合。

    Then C(n, k, S) = sum(C(n - s_i, k - 1, S[i:])) The summation is for every s_i from S. S[i:] means all the elements from S starting from i-th element to the end - we need this to prevent repeated combinations.

    初始条件为 C(0,0,_ )= 1 和 C(n,k,_)= 0 如果 n< 0 或 k< 0 或 n> 0 和 k < 1 。

    The initial conditions are C(0, 0, _) = 1 and C(n, k, _) = 0 if n < 0 or k < 0 or n > 0 and k < 1 .

    您要计算的数字:

    R = sum(C(i,k,S)* C(n-i,k,S))对于 i = 1..n-1 , k = 1..min(i,ni)/ Smin 其中, Smin -最小 S 中的硬币面额。

    R = sum(C(i, k, S) * C(n - i, k, S)) for i = 1..n-1, k = 1..min(i, n-i)/Smin where Smin - the smallest coin denomination from S.

    值 min(i,ni)/ Smin 表示对硬币进行分区时可能出现的最大硬币数量给定的总和。例如,如果总和 n = 20 和 i = 8 (第一个人获得$ 8,第二个人获得$ 12),最小硬币面额是2美元,最大硬币数目是 8/2 = 4 。 > 4 硬币无法获得$ 8。

    The value min(i, n-i)/Smin represents the maximum number of coins that is possible when partitioning the given sum. For example if the sum n = 20 and i = 8 (1st person gets $8, 2nd gets $12) and the minimum coin denomination is $2, the maximum possible number of coins is 8/2 = 4. You can't get $8 with >4 coins.

    更多推荐

    多种代币兑换的动态编程解决方案

    本文发布于:2023-11-29 01:56:01,感谢您对本站的认可!
    本文链接:https://www.elefans.com/category/jswz/34/1644830.html
    版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
    本文标签:代币   多种   解决方案   动态

    发布评论

    评论列表 (有 0 条评论)
    草根站长

    >www.elefans.com

    编程频道|电子爱好者 - 技术资讯及电子产品介绍!