5

我编写了一个用于生成子集总和的程序，该程序可用于此问题，其中指出：

假设你有 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数字减去配置（这实际上是方式[ v - (n1 + 1)x1 ] ）。此外，如果我们只使用$x2的n2个数字，我们还必须减去方式[ v - (n2 + 1)x2 ]，等等。

现在，我们已经两次减去至少使用 ( n1 + 1) $x1和 ( n2 + 1) $x2的配置，因此我们需要添加方式[ v -(n1 + 1)x1 - (n2 + 1) x2 ] 等。

特别是，如果，

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

Ai = 至少使用ni + 1 个$xi的配置集，对于 1 <= i <= m，则

我们正在寻求的结果 = | N | - | A1 | - | A2 | .. - | 上午| + | A1和A2 | + | A1和A3 | + ... - | A1和A2和A3 | ......

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

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]];
    }
}
4

2 回答 2

4

让我们假设你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]];

你仍然可以应用你的模数并计算你的极限，为了简单起见，我把它们省略了。

于 2010-11-16T21:22:10.297 回答
-4

该问题被命名为“硬币问题”，并且被称为 NP-hard。

你可以在这里稍微了解 一下。

于 2010-11-16T20:08:34.323 回答