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

- [Người hướng dẫn] Bài toán tạo thay đổi đã trở thành một thứ gì đó cổ điển do những gì nó có thể cho chúng ta thấy về các cách tiếp cận khác nhau để giải quyết vấn đề bằng thuật toán. Trong video này, chúng ta sẽ xem xét cách nó có thể được giải quyết bằng cách sử dụng phương pháp tham lam. Vì vậy, mục tiêu của bài toán là tìm số lượng đồng xu nhỏ nhất từ một tập hợp các mệnh giá cộng lại thành một lượng tiền nhất định. Ví dụ: ở Vương quốc Anh, chúng tôi có một xu, hai xu, năm xu, 10 xu, 20 xu, 50 xu, một bảng Anh và hai xu. Vì vậy, từ tập hợp các đồng xu này, số lượng tối thiểu chúng ta có thể sử dụng để tạo ra giá trị là 24 pence là bao nhiêu? . Vì vậy, có lẽ bạn đã đưa ra câu trả lời giống như tôi ở đây. Đó là đồng xu 20 xu cộng với hai đồng xu hai xu là số tiền tối thiểu chúng tôi có thể sử dụng. Còn 1 cân 63 thì sao? . Vì vậy, chúng ta có thể sử dụng đồng xu một bảng Anh, đồng xu 50 xu, đồng xu 10 xu, đồng xu hai xu và đồng xu một xu. Đó là mức tối thiểu mà…

Nội dung chính Show

Tải xuống các khóa học và học mọi lúc, mọi nơi
Cách tiếp cận để giải quyết vấn đề thay đổi tiền xu
Mã cho vấn đề đổi xu
Tiền xu trong giải pháp tối ưu
Phân tích thuật toán
thay đổi là gì
Vấn đề thay đổi tiền xu có nghĩa là gì?
Bài toán đổi xu trong quy hoạch động là gì?
Vấn đề đổi xu NP có khó không?

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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

Hãy bắt đầu bằng cách tạo một mảng để lưu trữ số xu tối thiểu cần thiết cho mỗi giá trị 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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

Chúng tôi biết rằng với giá trị bằng 0, không cần xu nào cả

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

Bây giờ, chúng ta cần lặp lại từng giá trị trong mảng M và điền vào. Ngoài ra, để lưu trữ số xu tối thiểu cho mỗi giá trị, chúng tôi sẽ tạo một biến và khởi tạo nó với $\infty$ để tất cả các giá trị khác nhỏ hơn nó khi bắt đầu. Nó tương tự như biến 'maximum_revenue' mà chúng ta đã tạo trong chương trước

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

Bây giờ với mỗi j, chúng ta cần chọn giá trị nhỏ nhất là $M_{n-d_i}+1$, trong đó $d_i$ sẽ thay đổi từ $d_1$ thành $d_k$ và do đó, tôi sẽ thay đổi từ 1 thành k. Ngoài ra, nếu giá trị của $d_i$ lớn hơn j (giá trị cần tạo) thì đương nhiên chúng ta không thể sử dụng đồng xu đó

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

9 → Chúng tôi đang lặp lại để thay đổi giá trị của $d_i$ từ $d_1$ thành $d_k$

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

00 → Nếu giá trị được tạo ra (j) lớn hơn giá trị của đồng xu hiện tại (d[i]), chỉ khi đó chúng ta mới có thể sử dụng đồng xu này

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

01 → Nếu giá trị hiện tại của M[j-d[i]] (hoặc $M_{j-d_i}$) nhỏ hơn giá trị tối thiểu hiện tại, thì chúng tôi sẽ thay đổi giá trị của 'tối thiểu'

Bây giờ chúng ta chỉ cần thay đổi giá trị của mảng M thành giá trị nhỏ nhất đã tính toán và trả về

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

Tiền xu trong giải pháp tối ưu

Giả sử chúng ta biết đồng tiền đầu tiên cần thiết để có được giải pháp tối ưu cho từng giá trị. Bây giờ, chúng ta có thể trừ đi giá trị của đồng xu đầu tiên từ $n$ và sau đó chúng ta sẽ có một giá trị khác được tạo ra

Như đã thảo luận ở trên, vấn đề thể hiện cấu trúc con tối ưu và chúng tôi biết đồng xu đầu tiên cần thiết để tạo ra giá trị mới này, vì vậy chúng tôi biết đồng xu thứ hai cần thiết để tạo ra giá trị $n$

Chúng tôi có thể lặp lại quy trình này để nhận được tất cả số tiền cần thiết

Vì vậy, vấn đề là chúng ta chỉ cần lưu trữ đồng xu đầu tiên cần thiết cho mỗi giá trị và sau đó chúng ta có thể nhận được đồng tiền tối ưu cho bất kỳ giá trị nào

Vì vậy, chúng tôi sẽ sửa đổi mã trên và lưu trữ các đồng tiền đầu tiên của mỗi giá trị trong một mảng S

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

08 → Chúng ta đang khai báo mảng S

Chúng tôi vừa phá vỡ chức năng 'min' từ đoạn mã trên

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

09 thành

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

10. Trong trường hợp này, chúng ta cũng đang gán giá trị của i cho biến 'coin' vì đồng xu 'i' này đang cho chúng ta giá trị nhỏ nhất và do đó, nó sẽ là đồng xu được lưu trữ trong mảng S

Cuối cùng, chúng tôi đang lưu trữ giá trị này trong mảng S

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

Như đã nói ở trên, trước tiên chúng ta in giá trị của đồng xu (S[l] sẽ cho chúng ta đồng xu và d[S[l]] là giá trị của đồng xu đó). Sau đó, giá trị ban đầu của chúng tôi đã giảm xuống bằng giá trị của đồng tiền tô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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

12 và chúng tôi đang làm điều này cho đến khi chúng tôi có giá trị lớn hơn 0

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

Phân tích thuật toán

Vòng lặp đầu tiên đang lặp lại từ 1 đến n và do đó có thời gian chạy là $\Theta(n)$. Vòng lặp cuối cùng cũng sẽ chạy tổng cộng n lần trong trường hợp xấu nhất (nó có thể chạy nhanh hơn tùy thuộc vào giá trị của

#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<=n; j++) {
    int minimum = INF;

    for(i=1; i<=k; i++) {
      if(j >= d[i]) {
        minimum = MIN(minimum, 1+M[j-d[i]]);
      }
    }
    M[j] = minimum;
  }
  return M[n];
}

int main() {
  // array starting from 1, element at index 0 is fake
  int d[] = {0, 1, 2, 3};
  printf("%d\n", coin_change(d, 5, 3)); //to make 5. Number of denominations = 3
  return 0;
}

14). Do đó, nó có thời gian chạy là $O(n)$

Bây giờ, cũng có một vòng lặp lồng nhau. Vòng lặp đầu tiên nếu lặp từ 1 đến n và vòng lặp thứ hai lặp từ 1 đến k và do đó, tổng thời gian chạy là $\Theta(nk)$. Tất cả các câu lệnh khác là câu lệnh lấy thời gian không đổi. Như vậy thuật toán có thời gian chạy là $\Theta(nk)$

Còn nhiều thuật toán thú vị khác được tối ưu hóa bằng quy hoạch động. Bạn có thể viết về chúng trên BlogsDope hoặc có thể tải xuống ứng dụng BlogsDope để không bao giờ bỏ lỡ bất kỳ bài viết mới nào

thay đổi là gì

Bài toán đổi tiền giải quyết câu hỏi tìm số lượng đồng xu (có mệnh giá nhất định) tối thiểu để tạo thành một số tiền nhất định. It is a special case of the integer knapsack problem, and has applications wider than just currency.

Vấn đề thay đổi tiền xu có nghĩa là gì?

Bạn được cung cấp một loạt tiền xu với các mệnh giá khác nhau và một số nguyên thể hiện tổng số tiền; . you must return the fewest coins required to make up that sum; if that sum cannot be constructed, return -1.

Bài toán đổi xu trong quy hoạch động là gì?

Bài toán đổi xu là thuật toán cuối cùng chúng ta sẽ thảo luận trong phần lập trình động này. Trong bài toán đổi xu, về cơ bản, chúng ta được cung cấp các đồng xu có mệnh giá khác nhau như 1¢, 5¢ và 10¢. Bây giờ, chúng ta phải kiếm một số tiền bằng cách sử dụng những đồng xu này sao cho số lượng đồng xu tối thiểu được sử dụng .

Vấn đề đổi xu NP có khó không?

Trừu tượng. Vấn đề tạo ra sự thay đổi là vấn đề biểu diễn một giá trị nhất định với ít đồng xu nhất có thể từ một tập hợp các mệnh giá đồng xu nhất định. Để giải quyết vấn đề này đối với các hệ thống tiền tùy ý là NP-hard [L].

programming python

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

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

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

Tiền xu trong giải pháp tối ưu

Phân tích thuật toán

thay đổi là gì

Vấn đề thay đổi tiền xu có nghĩa là gì?

Bài toán đổi xu trong quy hoạch động là gì?

Vấn đề đổi xu NP có khó không?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội