硬币数量有限的硬币找零

  • Z时代
  • 2024-01-10
  • 分类：问答

我已经编写了一个生成子集总和的程序，该程序可能会在以下问题中使用：

假设您有3张1美元硬币，2张2美元硬币，3张5美元硬币，1张10美元硬币，有4种方法可从这些硬币中获得10美元。如果有n1个$ X1硬币，n2个$

X2硬币.... nm $ Xm个硬币，我们可以从这些数量有限的硬币中获得$ X个方法？

如果我们创建一组{X1，X1 ..... X1，X2，X2 .......... X2，…，…，.......... ..，Xm，Xm …

Xm}，然后对其进行子集求和，当然我们可以得到$ X的结果。但是我找不到一种使用集合{n1，n2，n3 .... nm}，{X1，X2，X3 ....

Xm}的方法。一位朋友告诉我，这是背包问题的一种变体，但我不确定如何。

这是我写的部分代码：

ways[0]=1, mylim=0;
for(i=0;i<count;i++){
    if(mylim+coins[i]<=LIMIT) mylim+=coins[i];
    else mylim=LIMIT;
    for(j=mylim; j>=coins[i];j--){
        ways[j]=(ways[j]+ways[j-coins[i]])%MOD;
    }
}

如果您足够友好地进行详细说明，那对我来说将是很棒的。

：这个问题更适合用于计算机科学的stackexchange，但是由于这是我的一个老问题，所以我在这里进行编辑。

这个问题可以用 原理来解决， 当我们固定硬币值，但是每个查询的每个硬币的数量 ，这个问题就很方便了。

假设 Ways [v] 是用 $ x1 ， $ x2 ，.. $ xm 制作 $ v的 方法，每种方法需要使用多次。现在，如果我们只使用

N1 的数字 $ X1 ，我们必须减去至少使用（配置 N1 + 1）号的 $ X1 （这实际上是 方法 [ N - （N1 +

1）×1 ]）。此外，如果我们只使用 N2 的数字 $ X2 ，我们必须减去 途径 [ N - （N2 + 1）×2 ]，以及，等 __

现在，我们两次减去了至少使用（ n1 + 1） $ x1 和（ n2 + 1） $ x2 的配置，因此我们需要添加 方法 [

v-（n1 + 1）x1-（n2 + 1） x2 ]等

特别是如果

=尽可能多使用所有硬币的一组配置，

=一组配置，其中至少使用 ni + 1个 $ xi的 数字，对于1 <= i <= m ，则

我们寻求的结果= | | -| | -| | ..-| | + | 和 |

+ | 和 | + …-| 和 和 | .....

计算无限制硬币配置数量的代码实际上更简单：

ways[0]=1;
for( int i = 0 ; i < count ; i++){
    for( int j = coins[i] ; j < ways.size() ; j++ ){
        ways[j] += ways[j-coins[i]];
    }
}

回答：

假设您全部ni是1。

让ways[j] = number of ways of obtaining sum j。

您可以这样计算（这是您正在做的，但是我不知道您为什么命名变量primes）。

ways[0] = 1
for i = 1 to m do
    for j = myLim downto X[i] do
        ways[j] += ways[j - X[i]];

这意味着每个价值硬币只使用Xi一次。您可以添加另一个循环以至少一次且最多一次使用它ni：

ways[0] = 1
for i = 1 to m do
    for times = 1 to n[i] do // use Xi one time, then two times, then three, ..., then ni
        for j = myLim downto times*X[i] do
            ways[j] += ways[j - times*X[i]];

您仍然可以应用模并计算极限，为简单起见，我将其省略。

以上是 硬币数量有限的硬币找零 的全部内容， 来源链接： utcz.com/qa/416712.html

回到顶部