动态编程 - C中的最小硬币数

Question

我已经浏览了网站上的各种问题,我没有设法通过以下推理找到任何实现这一点的东西(所以我希望这不是重复).

我试图通过C程序解决的问题如下:

作为自动售货机控制器的程序员,您需要计算构成所需更改的最小硬币数量,以便回馈给客户.这个问题的有效解决方案采用动态编程方法,首先计算1美分变化所需的硬币数量,然后计算2美分,然后计算3美分,直到达到所需的变化,每次使用先前的计算硬币数量.编写一个包含该功能的程序,该程序ComputeChange()获取有效硬币列表和所需的更改.该程序应反复询问控制台所需的更改并进行相应的调用ComputeChange().它还应该使用"缓存",其中保留任何先前计算的中间值以用于后续查找.

在网上四处寻找其他人如何解决它后,我发现下面的例子应用了便士,镍币和硬币:

我尝试以我的代码为基础.但首先,我的代码没有停止,其次,我不确定我是否合并了上面的标题中提到的缓存元素.(我不确定我需要去做那个部分).

任何人都可以帮我找到代码中的缺陷吗？

#include <stdio.h>
#include <limits.h>

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 < n; i++){
        if((i>=0) && (a[i]< min))
            min = a[i];
    }
    return min;
}

任何帮助将不胜感激.

Answer 1

即使进行了修正，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[n-i-1], n, count_now+1, bestcount);