2013-02-21 21 views
15

tôi đang tìm kiếm một giải pháp tốt cho Change-making problem và tôi thấy mã này (Python):Hiểu thay đổi thuật toán làm

target = 200 
coins = [1,2,5,10,20,50,100,200] 
ways = [1]+[0]*target 
for coin in coins: 
    for i in range(coin,target+1): 
     ways[i]+=ways[i-coin] 
print(ways[target]) 

Tôi không có vấn đề hiểu biết những gì mã theo nghĩa đen có, nhưng tôi không thể hiểu TẠI SAO nó hoạt động. Bất cứ ai cũng có thể giúp đỡ?

Trả lời

11

Để có được tất cả các bộ có thể là yếu tố này là tương đương với 'a' hoặc 'b' hoặc 'c' (tiền xu của chúng tôi) rằng số tiền lên đến 'X' bạn có thể:

  • Mang tất cả bộ như vậy cộng lại Xa và thêm một 'a' cho mỗi cái.
  • Thực hiện tất cả các bộ như vậy tổng hợp thành X-b và thêm một số 'b' cho mỗi bộ.
  • Thực hiện tất cả các bộ như vậy tổng hợp thành X-c và thêm một 'c' vào mỗi bộ.

Vì vậy, số cách bạn có thể nhận X là tổng số cách bạn có thể nhận được X-a và X-b và X-c.

ways[i]+=ways[i-coin] 

Phần còn lại là sự lặp lại đơn giản.

tắm gợi ý: lúc bắt đầu bạn có thể thiết lập với tổng zero trong đúng một cách (trống bộ)

ways = [1]+[0]*target 
8

Đây là một ví dụ cổ điển của dynamic programming. Nó sử dụng bộ nhớ đệm để tránh sự đổ vỡ của đếm những thứ như 3 + 2 = 5 hai lần (vì một giải pháp có thể khác: 2 + 3). Một thuật toán đệ quy rơi vào lỗ hổng đó. Hãy tập trung vào một ví dụ đơn giản, trong đó target = 5coins = [1,2,3].Các đoạn mã bạn được đăng đếm:

  1. 3 + 2
  2. 3 + 1 + 1
  3. 2 + 2 + 1
  4. 1 + 2 + 1 + 1
  5. 1 + 1 + 1 + 1 + 1

trong khi đếm phiên bản đệ quy:

  1. 3 + 2
  2. 2 + 3
  3. 3 + 1 + 1
  4. 1 + 3 + 1
  5. 1 + 1 + 3
  6. 2 + 1 + 2
  7. 1 + 1 + 2
  8. 2 + 2 + 1
  9. 2 + 1 + 1 + 1
  10. 1 + 2 + 1 + 1
  11. 1 + 1 + 2 + 1
  12. 1 + 1 + 1 + 2
  13. 1 + 1 + 1 + 1 + 1

code đệ quy:

coinsOptions = [1, 2, 3] 
def numberOfWays(target): 
    if (target < 0): 
     return 0 
    elif(target == 0): 
     return 1 
    else: 
     return sum([numberOfWays(target - coin) for coin in coinsOptions]) 
print numberOfWays(5) 

động lập trình:

target = 5 
coins = [1,2,3] 
ways = [1]+[0]*target 
for coin in coins: 
    for i in range(coin, target+1): 
     ways[i]+=ways[i-coin] 
print ways[target] 
4

Ý tưởng chính đằng sau các mã như sau: " Trên mỗi bước có ways các cách để thực hiện thay đổi i số tiền đã cho tiền xu [1,...coin] ".

Vì vậy, trong lần lặp đầu tiên, bạn chỉ có một đồng xu có mệnh giá là 1. Tôi tin rằng nó là hiển nhiên để thấy rằng chỉ có một cách để cung cấp cho một sự thay đổi chỉ có những đồng tiền cho bất kỳ mục tiêu. Ở bước này, ways mảng sẽ trông giống như [1,...1] (chỉ một cách cho tất cả các mục tiêu từ 0 đến target).

Trong bước tiếp theo, chúng tôi thêm một đồng xu có mệnh giá là 2 vào tập hợp tiền xu trước đó. Bây giờ chúng tôi có thể tính toán số lượng kết hợp thay đổi có cho mỗi mục tiêu từ 0 đến target. Rõ ràng, số lượng kết hợp sẽ chỉ tăng cho các mục tiêu> = 2 (hoặc đồng tiền mới được thêm vào, trong trường hợp chung). Vì vậy, đối với mục tiêu bằng 2 số kết hợp sẽ là ways[2](old) + ways[0](new). Thông thường, mỗi khi i bằng một đồng xu mới được giới thiệu, chúng tôi cần thêm 1 vào số kết hợp trước đó, trong đó một kết hợp mới sẽ chỉ bao gồm một đồng xu.

Đối target>2, câu trả lời sẽ bao gồm tổng của "tất cả các kết hợp của target lượng có tất cả tiền xu ít hơn coin" và "tất cả các kết hợp của coin lượng có tất cả tiền xu ít hơn coin chính nó".

Ở đây tôi mô tả hai bước cơ bản, nhưng tôi hy vọng sẽ dễ dàng khái quát hóa nó.

Hãy để tôi cho bạn thấy một cây tính toán cho target = 4coins=[1,2]:

cách [4] đồng tiền trao = [1,2] =

cách [4] đồng tiền trao = [1] + cách [2] đồng tiền trao = [1,2] =

1 + cách [2] đồng tiền trao = [1] + cách [0] đồng tiền trao = [1,2] =

1 + 1 + 1 = 3

Vì vậy, có ba cách để thay đổi: [1,1,1,1], [1,1,2], [2,2].

Mã được đưa ra ở trên hoàn toàn tương đương với giải pháp đệ quy. Nếu bạn hiểu the recursive solution, tôi đặt cược bạn hiểu giải pháp được đưa ra ở trên.

0

Giải pháp mà bạn đã đăng là tóm tắt phiên bản của mã này.

/// <summary> 
    /// We are going to fill the biggest coins one by one. 
    /// </summary> 
    /// <param name="n"> the amount of money </param> 
    public static void MakeChange (int n) 
    { 
     int n1, n2, n3; // residual of amount after each coin 
     int quarter, dime, nickel; // These are number of 25c, 10c, 5c, 1c 
     for (quarter = n/25; quarter >= 0; quarter--) 
     { 
      n1 = n - 25 * quarter; 
      for (dime = n1/10; dime >= 0; dime--) 
      { 
       n2 = n1 - 10 * dime; 
       for (nickel = n2/5; nickel >= 0 && (n2 - 5*nickel) >= 0; nickel--) 
       { 
        n3 = n2 - 5 * nickel; 
        Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, n3); // n3 becomes the number of cent. 
       } 
      } 
     } 
    }