動態編程 - 最小硬幣高速緩存

Question

早些時候，我發佈了關於硬幣自動售貨機問題的question（所需的最少硬幣數量）。原來這個問題是for循環中的一個輸入錯誤，所以現在程序起作用了。原來的問題是這樣的：

當你需要計算硬幣組成需要改變，以回饋客戶的最小數量的自動售貨機控制器的編程。這個問題的一個有效解決方案需要一個動態規劃方法，首先計算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 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; 
} 

我已經張貼使用循環在你前面的問題的解決方案。我會在這裏再次發佈：

所以下面是你的問題使用memoization和動態編程的代碼片段。複雜度爲O（Val * numTypesofCoins）。

最後，更改[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; 

    } 
}