动态规划 - 在C币的最小数量 [英] Dynamic Programming - Minimum number of coins in C

问题描述

我已经通过该网站上的各种问题看，我还没有设法找到任何这由以下推理（所以我希望这不是一个重复的）。

I have looked through various questions on the site and I haven't managed to find anything which implements this by the following reasoning (so I hope this isn't a duplicate).

我想通过C程序来解决的问题是：

The problem I'm trying to solve via a C program is the following:

由于自动售货机控制器的程序员你需要计算硬币组成所需要的变化回馈客户的最低数量。一个有效的解决这个问题需要一个动态规划方法，出发计算了1美分变化所需要的硬币数量，那么2美分，那么3美分，直至达到所要求的变化，每次利用事先计算的硬币的数目。编写包含功能的程序 ComputeChange（），这需要有效的硬币和所需变化的列表。该计划应反复询问从控制台需要的变化，并调用 ComputeChange（）相应。还应该充分利用缓存，其中的previously计算的中间值被保留为后续查询的。

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.

东张西望网上找其他人如何解决它之后，我发现便士，分毫应用下面的例子：

After looking around online to find how others have solved it, I found the following example applied with pennies, nickels and dimes:

这点我尝试在立足我的code。但首先，我的code不是停止，其次，我不知道如果我结合了的缓存的在上面的栏目提到的元素。 （我真的不知道我该怎么需要去有关的部分）。

Which I tried to base my code upon. But first of all, my code isn't halting, and secondly, I'm not sure if I'm incorporating the caching element mentioned in the rubric above. (I'm not really sure how I need to go about that part).

谁能帮助找到我的code中的缺陷？

Can anyone help find the flaws in my code?

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

任何援助将大大AP preciated。

Any assistance will be greatly appreciated.

推荐答案

OP的提供更改（）算法即被的地段的递归，即使在如果（v＆小于0）返回INT_MAX; 校正。这么多的递归，即使是小十岁上下的值将数以百万计的递归调用。

OP's supplied Change() algorithm incurs lots of recursion, even with the if(v < 0) return INT_MAX; correction. So much recursion that even small-ish values take millions of recursive calls.

一个简单的改进是缓存迄今为止发现的最佳解决方案。然后，当一个中间解决方案已经比最好的更糟糕，没有必要继续这条道路。

A simple improvement is to "cache" the best solution found so far. Then when an intermediate solution is already worse than the best, no need to continue that path.

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

一个次要的改进是第一使用大硬币尝试

A secondary improvement is to attempt using large coins first

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

这篇关于动态规划 - 在C币的最小数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！