Thay đổi đồng tiền tối ưu hóa lập trình động

Question

Tôi đã xem xét một số vấn đề lập trình động và tôi đã gặp khó khăn trong việc tìm kiếm số tiền nhỏ nhất để thay đổi.

Giả sử chúng ta có đồng xu trị giá 25, 10 và 1 và chúng tôi đang thực hiện thay đổi cho 30. Tham lam sẽ trả về 25 và 5 (1) trong khi giải pháp tối ưu sẽ trả về 3 (10). Đây là mã từ cuốn sách về vấn đề này:

def dpMakeChange(coinValueList,change,minCoins): 
    for cents in range(change+1): 
     coinCount = cents 
     for j in [c for c in coinValueList if c <= cents]: 
      if minCoins[cents-j] + 1 < coinCount: 
       coinCount = minCoins[cents-j]+1 
     minCoins[cents] = coinCount 
    return minCoins[change] 

Nếu ai đó có thể giúp tôi quấn quanh mã này (dòng 4 là nơi tôi bắt đầu nhầm lẫn), điều đó thật tuyệt. Cảm ơn!

Answer 1

Dường như với tôi như mã đang giải quyết vấn đề cho mỗi giá trị cent lên cho đến khi giá trị cent mục tiêu. Cho một giá trị đích v và một tập tiền xu C, bạn biết rằng đồng xu lựa chọn tối ưu S phải có dạng union(S', c), nơi c là một số xu từ C và S' sự là giải pháp tối ưu cho v - value(c) (tha ký hiệu của tôi). Vì vậy, vấn đề có optimal substructure. Cách tiếp cận lập trình động là giải quyết mọi vấn đề con có thể. Phải mất cents * size(C) bước, trái ngược với một cái gì đó mà thổi lên nhanh hơn nhiều nếu bạn chỉ cố gắng để brute lực lượng các giải pháp trực tiếp.

def dpMakeChange(coinValueList,change,minCoins): 
    # Solve the problem for each number of cents less than the target 
    for cents in range(change+1): 

     # At worst, it takes all pennies, so make that the base solution 
     coinCount = cents 

     # Try all coin values less than the current number of cents 
     for j in [c for c in coinValueList if c <= cents]: 

      # See if a solution to current number of cents minus the value 
      # of the current coin, with one more coin added is the best 
      # solution so far 
      if minCoins[cents-j] + 1 < coinCount: 
       coinCount = minCoins[cents-j]+1 

     # Memoize the solution for the current number of cents 
     minCoins[cents] = coinCount 

    # By the time we're here, we've built the solution to the overall problem, 
    # so return it 
    return minCoins[change] 

Answer 2

Tôi nghĩ rằng dòng thứ tư là khó hiểu vì trong khi Python có thể chọn/lọc trong một danh sách hiểu (transform(x) for x in iterable if condition(x)), nó không thể làm như vậy trong for x in iterable: biểu hiện tiêu chuẩn của nó.

Vì vậy, một người (cheesy imo) cách mọi người có được xung quanh đó là để hàn hai với nhau. Họ tạo ra một danh sách hiểu mà thực sự không có biến dạng (do đó, c for c in coinValueList) chỉ để họ có thể thêm các khoản if c <= cents trên. Và sau đó sử dụng nó như là iterable cho một biểu thức tiêu chuẩn for x in iterable:. Tôi nghi ngờ đó là nơi một số sự nhầm lẫn của bạn đến từ.

Một cách thay thế để đã viết dòng mà có thể đã được:

... 
for eachCoinValue in filter(lambda x: x <= cents, coinValueList): 
... 

Hoặc thậm chí rõ ràng hơn, với một "biến để lộ ý định" sẽ là:

... 
smallEnoughCoins = filter(lambda each: each <= cents) 
for each in smallEnoughCoins: 
    ... 

Answer 3

Dưới đây là một cách để suy nghĩ về vấn đề thay đổi đồng xu có thể hữu ích, nếu bạn cảm thấy thoải mái với lý thuyết đồ thị.

Giả sử bạn có một đồ thị được xác định theo cách sau:

• Có một nút cho mỗi đơn vị tiền (ví dụ, đồng xu) từ 0 lên đến giá trị mà bạn đang quan tâm (ví dụ, 39 cent hoặc bất kỳ thứ gì.)
• Có một vòng cung giữa hai nút được phân tách bằng chính xác giá trị của đồng xu bạn được phép sử dụng (ví dụ: nút giữa 34 xu và 29 xu nếu bạn được phép sử dụng nickels.)

Bây giờ bạn có thể nghĩ về vấn đề thay đổi đồng xu làm p ngắn nhất ath vấn đề từ giá trị của bạn quan tâm xuống không, bởi vì số lượng tiền xu sẽ được chính xác giống như số lượng vòng cung trong đường dẫn của bạn.

Thuật toán không sử dụng thuật ngữ lý thuyết đồ thị, nhưng về cơ bản là giống nhau: Vòng lặp ngoài khác nhau trên tất cả "xu" (hoặc nút, trong khung lý thuyết đồ thị) và vòng lặp bên trong khác nhau, trên tất cả các cung (các giá trị trong coinValueList) từ vòng cung hiện tại đến vòng cung tiếp theo. Tất cả cùng nhau, họ đang tìm kiếm con đường ngắn nhất từ ​​số không đến giá trị bạn quan tâm. Tuy nhiên, theo truyền thống, chúng tôi tìm kiếm theo mặc định.)

Tôi thực sự bắt đầu hiểu được lập trình động khi tôi nhận ra nhiều vấn đề có thể được coi là vấn đề đồ thị. (Hãy cẩn thận, mặc dù-- không phải tất cả chúng đều có thể. Một số là siêu đồ thị, và một số có lẽ không phải vậy. Nhưng nó đã giúp tôi rất nhiều.)