c - 动态规划 - 最小硬币缓存

Question

早些时候我发布了一个question关于投币机问题(最少投币数量)。原来问题是 for 循环中的拼写错误，所以现在程序可以运行了。原来的问题是这样的:

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.

问题在于代码使用了递归，因此计算大值需要相当长的时间。使用缓存应该可以改善这个问题，但我不知道该怎么做。代码可以在下面找到。

#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 INT_MAX;
    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((a[i]>=0) && (a[i]< min))
            min = a[i];
    }
    return min;
}

Answer 1

使用您现有的代码:

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

int computeChange(int[],int,int);
int min(int[],int);
void initChange ();
int change [MAX]; //used for memoization



int main(){
    int cur[]={1,2,5,10,20,50,100,200};
    int n = sizeof(cur)/sizeof(int);
    int v;

    initChange ();
    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;
}

void initChange () {
    int i =0;
    for (i = 0; i < MAX; i++) {
        change[i] = INT_MAX;
    }
}

int computeChange(int cur[], int v, int n){
    if(v < 0)
        return INT_MAX;
    else if(v == 0)
        return 0;
    else{

        if (change[v] == INT_MAX) {
            int possible_mins[n], i;
            for(i = 0; i < n; i++){
                possible_mins[i]=computeChange(cur, v-cur[i], n);
            }
            change[v] = 1 + min(possible_mins, n); // memoization
        }
        return change[v];//you return the memoized value

    };
}

int min(int a[], int n){
    int min = INT_MAX, i;
    for(i = 0; i < n; i++){
        if((a[i]>=0) && (a[i]< min))
            min = a[i];
    }
    return min;
}

我已经在你之前的问题中发布了一个使用循环的解决方案。我会在这里再次发布:

下面是使用记忆化和动态规划解决您的问题的代码片段。复杂度为 O(Val*numTypesofCoins)。

最后，change[val] 会给你 val 的最小硬币数。

int main (void) {
    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.
    printf("Enter a value in euro cents: ");
    scanf("%d", &val);

    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;

    }
}