गतिशील प्रोग्रामिंग - परिवर्तन

Question

मुझे गतिशील सिक्का बदलने की समस्या के लिए कोड के अंतिम भाग को समझने में समस्या हो रही है। मैंने नीचे दिया गया कोड शामिल किया है।

मैं अंतिम else नहीं समझ सकता। क्या मुझे उस बिंदु पर लालची एल्गोरिदम का उपयोग करना चाहिए या क्या मैं तालिका में पहले से मौजूद मानों से उत्तर की गणना कर सकता हूं? मैंने इस समस्या को समझने की कोशिश करने पर कड़ी मेहनत की है और मुझे लगता है कि मैं बहुत करीब हूं। इस विधि को तालिका बनाने और रिकर्सन के बिना बड़ी समस्या को हल करने के लिए तालिका में संग्रहीत परिणामों का उपयोग करके परिवर्तन की निश्चित मात्रा बनाने के लिए आवश्यक न्यूनतम सिक्के मिलते हैं।

public static int minCoins(int[] denom, int targetAmount){ 
    int denomPosition; // Position in denom[] where the first spot 
         // is the largest coin and includes every coin 
         // smaller. 
    int currentAmount; // The Amount of money that needs to be made 
         // remainingAmount <= initalAmount 
    int[][] table = new int[denom.length][targetAmount+1]; 
    for(denomPosition = denom.length-1 ; denomPosition >= 0 ; denomPosition--) { 
     for(currentAmount = 0 ; currentAmount <= targetAmount ; currentAmount++){ 
      if (denomPosition == denom.length-1){ 
       table[denomPosition][currentAmount] = 
        currentAmount/denom[denomPosition]; 
      } 
      else if (currentAmount<denom[denomPosition]){ 
       table[denomPosition][currentAmount] = 
        table[denomPosition+1][currentAmount]; 
      } 
      else{   
       table[denomPosition][currentAmount] = 
        table[denomPosition+1][currentAmount]- 
        table[denomPosition][denom[denomPosition]]-1; 
      } 
     } 
    } 
    return table[0][targetAmount]; 
} 

Answer 1

सिक्का बदलने वाली समस्या को हल करने के लिए आपको लालची एल्गोरिदम पर स्विच करने की आवश्यकता नहीं है, आप इसे गतिशील प्रोग्रामिंग एल्गोरिदम के साथ हल कर सकते हैं। उदाहरण के लिए, इस तरह:

public int minChange(int[] denom, int targetAmount) { 

    int actualAmount; 
    int m = denom.length+1; 
    int n = targetAmount + 1; 
    int inf = Integer.MAX_VALUE-1; 

    int[][] table = new int[m][n]; 
    for (int j = 1; j < n; j++) 
     table[0][j] = inf; 

    for (int denomPosition = 1; denomPosition < m; denomPosition++) { 
     for (int currentAmount = 1; currentAmount < n; currentAmount++) { 
      if (currentAmount - denom[denomPosition-1] >= 0) 
       actualAmount = table[denomPosition][currentAmount - denom[denomPosition-1]]; 
      else 
       actualAmount = inf; 
      table[denomPosition][currentAmount] = Math.min(table[denomPosition-1][currentAmount], 1 + actualAmount); 
     } 
    } 

    return table[m-1][n-1]; 

} 

Answer 2

क्या आप इसे सोच रहे हैं? अगर हम अमेरिकी सिक्कों का उपयोग करके 68 सेंट बदलने की कोशिश कर रहे थे ...

'denom' {25, 10, 5, 1} होगा?

और उत्तर "2 क्वार्टर, 1 डाइम, 1 निकल, और 3 पैसा" = '2 + 1 + 1 + 3 = 7' नहीं होगा? तो समारोह को मूल्य 7 वापस करना चाहिए। सही?

Answer 3

यह वास्तव में इस एल्गोरिदम का सही संस्करण है।

public static int minChange(int[] denom, int targetAmount) { 
    int actualAmount; 
    int m = denom.length + 1; 
    int n = targetAmount + 1; 
    int inf = Integer.MAX_VALUE - 1; 

    int[][] table = new int[m][n]; 
    for(int i = 0; i< m; ++i) { 
     for (int j = 1; j < n; j++) { 
      table[i][j] = inf; 
     } 
    } 

    for (int denomPosition = 1; denomPosition < m; denomPosition++) { 
     for (int currentAmount = 1; currentAmount < n; currentAmount++) { 
      if (denom[denomPosition-1] <= currentAmount) { 
       // take 
       actualAmount = table[denomPosition][currentAmount - denom[denomPosition-1]]; 
      } 
      else { 
       actualAmount = inf; 
      }            // do not take 
      table[denomPosition][currentAmount] = Math.min(table[denomPosition-1][currentAmount], 1 + actualAmount); 
     } 
    } 

    return table[m-1][n-1]; 
} 

Answer 4

//this works perfectly ... 

public int minChange(int[] denom, int targetAmount) 
    { 

    int actualAmount; 
    int m = denom.length+1; 
    int n = targetAmount + 1; 
    int inf = Integer.MAX_VALUE-1; 

    int[][] table = new int[m][n]; 
    for (int j = 1; j < n; j++) 
     table[0][j] = inf; 

    for (int i = 1; i < m; i++) //i denotes denominationIndex 
    { 
     for (int j = 1; j < n; j++) //j denotes current Amount 
     { 
      if (j - denom[i-1] >= 0)//take this denomination value and subtract this value from Current amount 

       table[i][j] = Math.min(table[i-1][j], 1 + table[i][j - denom[i-1]]); 

      else 
       table[i][j] = table[i-1][j]; 

     } 
    } 




    //display array 
     System.out.println("----------------Displaying the 2-D Matrix(denominations and amount)----------------"); 
     for (int i = 0; i < m; i++) 
     { 
      System.out.println(" "); 
      for (int j = 0; j < n; j++) 
      { 
       System.out.print(" "+table[i][j]); 

      } 
      System.out.println(" "); 
     } 

    return table[m-1][n-1]; 

}