Vấn đề tạo thay đổi Python

Tải xuống các khóa học và học mọi lúc, mọi nơi

Xem các khóa học trên thiết bị di động của bạn mà không cần kết nối internet. Tải xuống các khóa học bằng ứng dụng LinkedIn Learning trên iOS hoặc Android của bạn

Trong số 4 cách kiếm 10¢ này, chúng ta có thể thấy rằng cách đầu tiên chỉ sử dụng một đồng xu 10¢ yêu cầu số lượng xu ít nhất và do đó, đó là giải pháp của chúng tôi

Vì vậy, trong bài toán đổi xu, chúng ta được cung cấp các loại tiền có mệnh giá khác nhau. $$ 1 = d_1 \lt d_2 \lt d_3 \lt. \lt d_k $$

$d_1 = 1$ đảm bảo rằng chúng tôi có thể kiếm được bất kỳ số tiền nào bằng cách sử dụng những đồng tiền này

Bây giờ, chúng tôi phải thực hiện thay đổi cho giá trị $n$ bằng cách sử dụng những đồng xu này và chúng tôi cần tìm ra số lượng xu tối thiểu cần thiết để thực hiện thay đổi này

Cách tiếp cận để giải quyết vấn đề thay đổi tiền xu

Giống như bài toán cắt thanh, bài toán đổi đồng xu cũng có tính chất của cấu trúc con tối ưu i. e. , giải pháp tối ưu của một vấn đề kết hợp giải pháp tối ưu cho các vấn đề con. Ví dụ: chúng tôi đang tạo một giải pháp tối ưu cho số tiền là 8 bằng cách sử dụng hai giá trị - 5 và 3. Vì vậy, giải pháp tối ưu sẽ là giải pháp trong đó 5 và 3 cũng được thực hiện tối ưu, nếu không, chúng ta có thể giảm tổng số xu tối ưu hóa các giá trị của 5 và 8

Sở dĩ ta kiểm tra xem bài toán có cấu trúc con tối ưu hay không vì nếu có cấu trúc con tối ưu thì khả năng cao là sử dụng quy hoạch động sẽ tối ưu được bài toán

Giả sử $M_n$ là số xu tối thiểu cần thiết để thực hiện thay đổi cho giá trị n

Hãy bắt đầu bằng cách nhặt đồng xu đầu tiên tôi. e. , đồng xu có giá trị $d_1$. Vì vậy, bây giờ chúng ta cần tạo giá trị của $n-d_1$ và $M_{n-d_1}$ là số xu tối thiểu cần thiết cho mục đích này. Vì vậy, tổng số xu cần có là $1+M_{n-d_1}$ [1 xu vì chúng ta đã chọn đồng xu có giá trị $d_1$ và $M_{n-d_1}$ là số xu tối thiểu cần để kiếm

Tương tự, chúng ta có thể chọn đồng xu thứ hai trước, sau đó cố gắng tìm giải pháp tối ưu cho giá trị của $n-d_2$, giải pháp này sẽ yêu cầu $M_{n-d_2}$ đồng xu và do đó tổng cộng là $1 + M_{n-d_2

Chúng ta có thể lặp lại quy trình với tất cả k xu và sau đó giá trị tối thiểu của tất cả những đồng này sẽ là câu trả lời của chúng ta. tôi. e. , $\min_{i. d_i \leq n} \{M_{n-d_i}+1\}$

Quá trình trên cũng có thể được hiểu theo một cách khác. Giả sử, chúng tôi đã chọn một đồng xu có giá trị x và chúng tôi biết rằng đồng xu này sẽ nằm trong giải pháp. Vì vậy, nhiệm vụ tiếp theo của chúng ta là tìm số xu tối thiểu cần thiết để thực hiện thay đổi giá trị n-x i. e. , $M_{n-x}$. Ngoài ra, bằng cách chọn đồng xu có giá trị x, chúng tôi đã tăng tổng số xu cần thiết lên 1. Vì vậy, chúng ta có thể viết. $$ M_n = 1+M_{n-x} $$

Nhưng vấn đề thực sự là chúng ta không biết giá trị của x. Vì vậy, chúng tôi sẽ thử mọi đồng xu cho giá trị của x và sau đó chúng tôi sẽ chọn mức tối thiểu trong số đó

$$ M_n = \begin{cases} \min_{i. d_i \leq n} \{M_{n-d_i}+1\}, &\text{if $n \gt 0$} \\[2ex] 0, &\text{if $n = 0$} \end

Bạn có thể thấy rằng có các bài toán con chồng chéo trong giải pháp của chúng tôi và do đó, chúng tôi có thể sử dụng lập trình động để tối ưu hóa điều này. Vì vậy, hãy xem cách triển khai mã hóa của công thức mà chúng tôi đã rút ra ở trên

Mã cho vấn đề đổi xu

Chúng tôi sẽ sử dụng triển khai từ dưới lên của lập trình động cho mã

Hàm của chúng ta sẽ cần các vectơ mệnh giá của đồng xu [d], giá trị cần thay đổi [n] và số lượng mệnh giá mà chúng ta có [k hoặc số phần tử trong mảng d] i. e. ,

#include 
#define MIN[x, y] [[[x] < [y]] ? [x] : [y]]

const int INF = 100000;

//k is number of denominations of the coin or length of d
int coin_change[int d[], int n, int k] {
  int M[n+1];
  M[0] = 0;

  int i, j;
  for[j=1; j