Xác định các kết hợp thực hiện thay đổi với một số tiền nhất định

Question

Nhiệm vụ của tôi là viết một thuật toán sử dụng lực lượng vũ phu để xác định số cách khác nhau, kết hợp thay đổi có liên quan với số tiền nhất định. Sự thay đổi sẽ được tạo ra bằng cách sử dụng các đồng tiền sau: penny (1 cent), nickel (5 cent), dime (10 cent) và quý (25 cent).

ví dụ:

Input: 16 (có nghĩa là một sự thay đổi của 16 cent)

Output: có thể được sản xuất trong 6 cách khác nhau và họ là:

1. 16 xu.
2. 11 xu, 1 niken
3. 6 đồng xu, 1 đồng xu
4. 6 đồng xu, 2 nickels
5. 1 xu, 3 nickels
6. 1 xu, 1 niken, 1 xu

My thuật toán phải tạo ra tất cả các kết hợp thay đổi có thể cho một số lượng thay đổi được chỉ định.

---

Tôi mất hoàn toàn về cách bắt đầu một thuật toán như thế này. Bất kỳ đầu vào hoặc cái nhìn sâu sắc để giúp tôi đi sẽ là tuyệt vời.

Answer 1

Ok. Hãy để tôi giải thích một ý tưởng cho một thuật toán brute force. Tôi sẽ sử dụng đệ quy ở đây.

Bạn cần thay đổi c xu. Sau đó xem xét c như

c = p * PENNY + n * NICKEL + d * DIME + q * QUARTER 

hoặc đơn giản,

c = (p * 1) + (n * 5) + (d * 10) + (q * 25) 

Bây giờ bạn cần phải đi qua tất cả các giá trị có thể cho p, n, d và q rằng bằng với giá trị của c. Sử dụng đệ quy, cho mỗi p in [0, maximumPennies] đi qua mỗi n in [0, maximumNickels]. Đối với mỗi n, hãy xem qua mỗi d in [0, maximumDimes]. Đối với mỗi d, hãy xem qua từng số q in [0, maximumQuarters].

p in [0, maximumPennies] AND c >= p 
    | 
    +- n in [0, maximumNickels] AND c >= p + 5n 
     | 
     +- d in [0, maximumDimes] AND c >= p + 5n + 10d 
      | 
      +- q in [0, maximumQuarters] AND c >= p + 5n + 10d + 25q 

Đối với bất kỳ sự bình đẳng nào trong các bước này, bạn có giải pháp.

Answer 2

Hãy thử sử dụng tính năng đệ quy trên trang này. Chức năng của bạn nên có hai tham số - giá trị tối đa bạn được phép sử dụng và số tiền còn lại để thanh toán (bạn cần đầu tiên để tránh lặp lại). Thực hiện chức năng theo cách như vậy: nếu nó ở trong một trường hợp tầm thường (ví dụ: 1, 5, 10 và bạn được phép lấy một xu, niken, xu) tương ứng in giải pháp tầm thường. Ngoài ra, đối với mỗi trường hợp, hãy thử lấy một đồng xu của tất cả các loại được phép (ví dụ: không lớn hơn mức tối đa cho phép) và tiếp tục đệ quy.

Hy vọng điều này sẽ hữu ích.

Answer 3

Bạn có thể bắt đầu suy nghĩ về vấn đề này bằng cách chia nó thành các vấn đề con giải quyết những vấn đề này và sau đó thay đổi vấn đề và điều chỉnh giải pháp của bạn.

Trong trường hợp của bạn, trước tiên bạn có thể thử giải quyết vấn đề chỉ bằng đồng xu (Chỉ với một giải pháp rõ ràng), sau đó nhìn vào nickels và pennies và xem tất cả các kết hợp ở đó. Để cải thiện điều này, bạn có thể sử dụng lại các giải pháp từ các giai đoạn trước đó trong thuật toán của mình.

Answer 4

Vâng, nếu bạn muốn giải pháp lực lượng vũ phu, bạn có thể bắt đầu với một số rất ngây thơ recursive approach. Nhưng để hiệu quả, bạn sẽ cần một dynamic programming approach.

Đối với phương pháp đệ quy:

1. find out the number of ways you can make using penny only. 
2. do the same using penny and nickel only. (this includes step 1 also) 
3. the same using penny, nickel and dime only (including step 2). 
4. using all the coins (with all previous steps). 

Bước 1 là đơn giản, chỉ có một cách để làm điều đó.

Đối với bước 2, đệ quy nên như thế này:

number of ways to make n cent using penny and nickel = 
    number of ways to make (n - [1 nickel]) using penny and nickel 
    + number of ways to make n cent using penny only 

Bước 3:

number of ways to make n cent using penny, nickel and dime = 
    number of ways to make (n - [1 dime]) using penny, nickel and dime 
    + number of ways to make n cent using penny and nickel only 

Bước 4 là tương tự.

Và một điều cần nhớ: bạn có thể kiếm 0 xu trong một cách (nghĩa là sử dụng đồng tiền không), đó là trường hợp cơ bản.

Answer 5

public class PrintAllCoinCombinations { 


    static int findChange(int arr[], int index , int value, String str){ 

     if(value == 0){ 
      System.out.println(str); 
      return 1; 
     } 
     if(index<0){ 
      return 0; 
     } 
     if(value<0){ 
      return 0; 
     } 

     int excl = findChange(arr,index-1,value,str); 

     str += " "+ arr[index]; 

     int incl = findChange(arr,index,value-arr[index],str); 

     return incl + excl; 

    } 

    public static void main(String [] arg){ 
     int arr[] = {1,5,10,25}; 
     String s = ""; 
     int result = findChange(arr,3,16,s); 
     System.out.println(result); 
    } 
}