动态编程 – C中的最小硬币数
我已经浏览了网站上的各种问题，我没有设法通过以下推理找到任何实现这一点的东西（所以我希望这不是重复）。
我试图通过C程序解决的问题如下：
作为自动售货机控制器的程序员，您需要计算构成所需更改的最小硬币数量，以便回馈给客户。 这个问题的有效解决方案采用动态编程方法，首先计算1美分变化所需的硬币数量，然后计算2美分，然后计算3美分，直到达到所需的变化，并且每次使用先前计算的硬币数量。 编写一个包含函数
ComputeChange()的程序，该函数获取有效硬币列表和所需的更改。 该程序应反复询问控制台所需的更改并相应地调用ComputeChange()。 它还应该使用“缓存”，其中保留任何先前计算的中间值以用于后续查找。
在网上四处寻找其他人如何解决它后，我发现以下示例应用了便士，镍币和硬币：
我尝试以我的代码为基础。 但首先，我的代码并没有停止，其次，我不确定我是否合并了上面标题中提到的缓存元素。 （我不确定我需要怎么做这个部分）。
任何人都可以帮助我找到代码中的缺陷吗？
#include #include int computeChange(int[],int,int); int min(int[],int); int main(){ int cur[]={1,2,5,10,20,50,100,200}; int n = sizeof(cur)/sizeof(int); int v; printf("Enter a value in euro cents: "); scanf("%d", &v); printf("The minimum number of euro coins required is %d", computeChange(cur, v, n)); return 0; } int computeChange(int cur[], int v, int n){ if(v < 0) return -1; else if(v == 0) return 0; else{ int possible_mins[n], i; for(i = 0; i < n; i++){ possible_mins[i]=computeChange(cur, v-cur[i], n); } return 1+min(possible_mins, n); }; } int min(int a[], int n){ int min = INT_MAX, i; for(i = 0; i =0) && (a[i]< min)) min = a[i]; } return min; }
任何帮助将不胜感激。
即使使用if(v < 0) return INT_MAX; OP提供的Change()算法也会产生大量递归if(v < 0) return INT_MAX; 更正。 如此多的递归，即使是小的值也需要数百万的递归调用。
一个简单的改进是“缓存”到目前为止找到的最佳解决方案。 然后，当中间解决方案已经比最好的解决方案更差时，不需要继续该路径。
int computeChange(int cur[], int v, int n, int count_now, int *bestcount) { if (count_now >= *bestcount) { return INT_MAX; } if (v < 0) { return INT_MAX; } if (v == 0) { *bestcount = count_now; return 0; } int min_count = INT_MAX; for (int i = 0; i < n; i++) { int count = computeChange(cur, v - cur[i], n, count_now+1, bestcount); if (count < min_count) { min_count = count + 1; } } return min_count; } int bc = INT_MAX; computeChange(cur, v, n, 0, &bc));
二次改进是首先尝试使用大硬币
// int count = computeChange(cur, v - cur[i], n, count_now+1, bestcount); int count = computeChange(cur, v - cur[ni-1], n, count_now+1, bestcount);
所以下面是使用memoization和动态编程的问题的代码片段。 复杂性是O（Val * numTypesofCoins）。
最后，更改[val]将为您提供val的最小硬币数量。
int change [MAX]; int cur[]={1,2,5,10,20,50,100,200}; int n = sizeof(a)/sizeof(int); int val= //whatever user enters to get the num of coins required. for (i=0; i <= val; i++) { change[i] = INT_MAX; } for (i=0; i < n; i++) { // change for the currency coins should be 1. change[cur[i]] = 1; } for (i=1; i <= val; i++) { int min = INT_MAX; int coins = 0; if (change[i] != INT_MAX) { // Already got in 2nd loop continue; } for (j=0; j < n; j++) { if (cur[j] > i) { // coin value greater than i, so break. break; } coins = 1 + change[i - cur[j]]; if (coins < min) { min = coins; } } change[i] = min; }
如果你有说x的总和和面额硬币说a1, a2, a3, a4.. （按递减顺序）那么答案就是 – > x/a1+(x%a2)/a3+((x%a2)%a3)/a4+...这应该有希望给出答案