0

我在编写动态算法来解决硬币找零问题时遇到问题，我得到的是：

arr[value] - 一个用 0 填充的全局数组，长度是我要求解的值；

a[n] - 带有硬币值的数组；

void dynamic(int n, int *a, int value) {
arr[0]=0;
for(int i=1;i<value;i++){;
    for(int j=0;j<n;j++){
        if(i==arr[j]) arr[i]=1;
        else{
            arr[i] = arr[i-1] + 1;          
        }
    }
}}

我知道我想如何做到这一点，但是，我不知道如何实现它。

示例：
假设我有硬币 1 4 10 15 40 和价值 37 来解决。我正在像这样填充 arr：
如果硬币值 = i 我做 arr[i] = 1; 对于下一个元素，只要 i 低于下一个硬币，我就放上一个值 +1，arr[i-1] + 1。
所以这应该像这样填充 arr[i] 1 = 1, 2 = 2, 3 = 3, 4 = 1, 5 = 2 依此类推，但我遗漏了一些东西，不知道如何按照我想要的方式填充它。

有人可以按照我想要的方式帮助它吗？我一直试图弄清楚它，但我发现没有什么是正确的。我什至使用递归编写了整个算法，但它太慢了，所以我需要重新编写它。

4

1 回答 1

0

你可能想要：

memset(arr,0,sizeof(arr));
arr[0]=1;
for(int i=0;i<n;++i)
    for(int j=a[i];j<value;++j)
        arr[j]+=arr[j-a[i]];

如果我理解正确，这应该是正确的，基本上这是实现递归的巧妙技巧......

f[i,j]=f[i-1,j]+f[i-1,j-a[i]];

显然这需要O(n Value)时间。

于 2013-02-16T06:13:19.880 回答