0

给定一个 N 值，如果我们想用 N 美分找零，并且我们有无限供应 S = { S1, S2, .. , Sm} 价值的硬币，我们可以用多少种方法来找零？硬币的顺序无关紧要。

我写了下面的代码，但它总是返回比实际答案少一个。我想知道这是否是编写解决方案的正确方法？

#include <stdio.h>

int ways=0;
int remember[100] = {0};

void foo(int coin_denomination[], int size, int sum)
{
    int i;
    printf("%d\n", sum);
    if (sum==0) {
        ways++; 
        return; 
    }   
    if (remember[sum]==1)
        return; 
    remember[sum] = 1;
    if (sum < 0)
        return; 
    for(i=0;i<size;i++)
        foo(coin_denomination, size, sum-coin_denomination[i]);
}

int main()
{
    int coin_denomination[] = {1, 2, 3}; 
    int sum = 5;

    foo(coin_denomination, sizeof(coin_denomination)/sizeof(coin_denomination[0]), sum);
    printf("%d\n", ways);
    return 0;
}
4

1 回答 1

2

您需要对foo方法进行一些更改。你的问题是，remember你没有计算一些解决方案的变量。变量的目标remember不正确，您用于不多次处理相同的硬币收藏，但您只保存硬币收藏的总和，并且可以通过多个硬币收藏获得总和（例如：1 1 1当1 2您选择第二个，remember[3]将是 1 并且没有通过这一点，缺少解决方案1 2 2）

需要其他不重复coin collection的方式，在这种情况下，添加一个参数表示coin_denomination正在处理的索引并且只允许处理之后的硬币，问题就解决了。

代码（使用 GCC 4.9.0 测试）：

#include <stdio.h>

int ways=0;

void foo(int coin_denomination[], int size, int sum, int coin_idx = 0)
{
    if (sum < 0)
        return;
    int i;
    printf("%d\n", sum);
    if (sum==0) {
        ways++; 
        return; 
    }   
    for(i=coin_idx;i<size;i++)
        foo(coin_denomination, size, sum-coin_denomination[i], i);
}

int main()
{
    int coin_denomination[] = {1, 2, 3}; 
    int sum = 5;

    foo(coin_denomination, sizeof(coin_denomination)/sizeof(coin_denomination[0]), sum);
    printf("%d\n", ways);
    return 0;
}
于 2014-08-03T05:55:23.477 回答