Thay đổi lập trình động

Question

Tôi đang gặp khó khăn trong việc tìm ra phần mã cuối cùng của mình cho một vấn đề thay đổi xu động động. Tôi đã bao gồm mã bên dưới.

Tôi không thể tìm ra số else cuối cùng. Tôi có nên sử dụng thuật toán tham lam tại thời điểm đó hay tôi có thể tính toán câu trả lời từ các giá trị đã có trong bảng? Tôi đã làm việc chăm chỉ để cố gắng hiểu vấn đề này và tôi nghĩ rằng tôi khá thân thiết. Phương pháp tìm số tiền tối thiểu cần thiết để tạo ra một số thay đổi nhất định bằng cách tạo một bảng và sử dụng các kết quả được lưu trữ trong bảng để giải quyết vấn đề lớn hơn mà không sử dụng đệ quy.

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

Bạn không cần phải chuyển sang thuật toán tham lam để giải quyết vấn đề thay đổi đồng xu, bạn có thể giải quyết nó bằng thuật toán lập trình động. Ví dụ: như thế này:

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

Bạn có đang suy nghĩ về điều này không? Nếu chúng tôi cố gắng cung cấp 68 xu thay đổi bằng tiền xu của Hoa Kỳ…

‘denom’ là {25, 10, 5, 1}?

Và câu trả lời không phải là “2, 1 xu, 1 niken và 3 xu” = ‘2 + 1 + 1 + 3 = 7’? Vì vậy, hàm sẽ trả về giá trị 7. Phải không?

Answer 3

Đây thực sự là phiên bản chính xác của thuật toán này.

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

}