硬币找零问题C++

我有写一个动态的算法来解决硬币找零问题，我有一个问题是这样的：硬币找零问题C++

ARR [值] - 一个全球性的阵列充满0，lenght价值我想解决;

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解决。我正在填写这样的数字：
如果硬币值= i我arr [i] = 1;对于下一个元素，只要我低于下一个硬币，我把之前的值+ 1，arr [i-1] +1。
所以这应该填充arr [i]像这样1 = 1,2 = 2,3 = 3，4 = 1，5 = 2等等，但我错过了一些东西，不知道如何以正确的方式填充它。

有人可以按照我想要的方式做到这一点吗？我一直在试图找出它，但没有发现是正确的。我甚至使用递归来编写整个算法，但它太慢了，所以我需要重新编写一遍。

来源

2011-03-16 Paul

听起来像家庭作业。你正在处理背包问题。对于任何“大型”输入，它总是会很慢：http://en.wikipedia.org/wiki/Knapsack_Problem – 2011-03-16 17:06:36

这不是一个家庭作业，如果它是我不会再按我想要的方式写入它。 – Paul 2011-03-16 17:08:21

相关SO问题：http://stackoverflow.com/questions/1518330/coin-change-problem-with-infinite-number-of-coins-of-each-denomination – AJG85 2011-03-16 17:48:58

你可能想：

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-16 06:13:19 phoeagon

硬币找零问题C++

回答

相关问题