c - 动态规划 - C 中的最小硬币数

Question

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

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

As the programmer of a vending machine controller your are required to compute the minimum number of coins that make up the required change to give back to customers. An efficient solution to this problem takes a dynamic programming approach, starting off computing the number of coins required for a 1 cent change, then for 2 cents, then for 3 cents, until reaching the required change and each time making use of the prior computed number of coins. Write a program containing the function ComputeChange(), that takes a list of valid coins and the required change. This program should repeatedly ask for the required change from the console and call ComputeChange() accordingly. It should also make use of “caching”, where any previously computed intermediate values are retained for subsequent look-up.

在网上查找其他人的解决方法后，我发现了以下适用于便士、五分硬币和一角硬币的示例:

我试图以此作为我的代码的基础。但首先，我的代码没有停止，其次，我不确定我是否合并了上面标题中提到的 caching 元素。 (我不太确定我需要如何处理那部分)。

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

#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);