Динамическое программирование - Минимальное количество монет в C

Я просмотрел различные вопросы на сайте, и мне не удалось найти ничего, что реализует это по следующим соображениям (так что я надеюсь, что это не дубликат).

Проблема, которую я пытаюсь решить с помощью программы 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;
}

Любая помощь будет принята с благодарностью.

Ответы

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

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;

}