Thuật toán quy hoạch động

Giới thiệu

Thuật toán quy hoạch động (dynamic programming) là một phương pháp giải quyết các bài toán tối ưu, dựa trên việc tìm kiếm một cách hệ thống các phương án tối ưu dựa trên những kết quả tối ưu của các phần con (sub-problems) của bài toán ban đầu. Thuật toán quy hoạch động thường được sử dụng cho các bài toán tối ưu có tính chất tổ hợp và có cấu trúc lặp lại trong việc giải quyết.

Ứng dụng của thuật toán quy hoạch động:

• Trong lĩnh vực khoa học máy tính, thuật toán quy hoạch động được sử dụng để giải quyết các bài toán tối ưu trong nhiều lĩnh vực khác nhau như lập trình động, mô hình hóa toán học, đồ thị, v.v…
• Trong lĩnh vực kinh tế, thuật toán quy hoạch động được sử dụng để tối ưu hóa quyết định kinh doanh, tài chính, lập kế hoạch sản xuất v.v…
• Trong lĩnh vực khoa học dữ liệu, thuật toán quy hoạch động được sử dụng để xây dựng các mô hình dự đoán và phân loại.

Các ví dụ cụ thể về ứng dụng của thuật toán quy hoạch động bao gồm:

• Tìm kiếm đường đi ngắn nhất trên đồ thị.
• Bài toán túi knapsack – Tìm kiếm tập hợp đồ vật có giá trị lớn nhất với giới hạn dung lượng cho phép.
• Bài toán chia tiền – Tìm cách phân chia số tiền nhỏ nhất sao cho đủ để trả lại số tiền cần trả và số tiền trả lại là nhỏ nhất.

Thuật toán quy hoạch động cũng được sử dụng rộng rãi trong lĩnh vực lập trình động, nơi nó có thể giúp tăng tốc độ và giảm thời gian chạy của chương trình.

Thuật toán quy hoạch động

Các bước thực hiện

Các bước thực hiện thuật toán quy hoạch động như sau:

1. Xác định và phân tích bài toán: Xác định bài toán cần giải quyết, cấu trúc của bài toán, đặc điểm và các điều kiện của bài toán.

2. Xác định phương pháp tối ưu: Xác định cách tối ưu hóa và tìm kiếm phương án tối ưu cho bài toán.

3. Xác định bài toán con (sub-problems): Chia bài toán ban đầu thành các bài toán con nhỏ hơn, có cùng cấu trúc và có thể giải quyết bằng các phương pháp tối ưu hóa.

4. Xây dựng bảng quy hoạch động: Tạo ra bảng quy hoạch động, một ma trận lưu trữ kết quả của các bài toán con và kết quả tối ưu của bài toán ban đầu.

5. Thiết lập công thức đệ quy: Thiết lập công thức đệ quy để tính toán kết quả tối ưu của các bài toán con, dựa trên kết quả đã tính toán trước đó.

6. Tính toán kết quả tối ưu của bài toán ban đầu: Tính toán kết quả tối ưu của bài toán ban đầu dựa trên bảng quy hoạch động và công thức đệ quy đã thiết lập ở bước trước.

7. Truy vết kết quả: Nếu cần, thực hiện truy vết để tìm ra phương án tối ưu của bài toán ban đầu từ bảng quy hoạch động.

8. Kiểm tra và tối ưu hóa: Kiểm tra kết quả và tối ưu hóa thuật toán nếu cần thiết.

Các bước trên có thể thực hiện theo thứ tự khác nhau tùy vào bài toán cụ thể, tuy nhiên cần đảm bảo bước đệ quy được thiết lập đúng để đảm bảo tính chính xác và hiệu quả của thuật toán quy hoạch động.

Cấu trúc của thuật toán quy hoạch động

Cấu trúc của thuật toán quy hoạch động bao gồm các phần sau:

1. Bảng quy hoạch động: Đây là một ma trận lưu trữ kết quả của các bài toán con và kết quả tối ưu của bài toán ban đầu. Bảng quy hoạch động được xây dựng bằng cách khởi tạo một ma trận có kích thước phù hợp với bài toán và tính toán kết quả tối ưu cho các bài toán con.

2. Hàm truy hồi (recurrence function): Đây là hàm đệ quy tính toán kết quả tối ưu của các bài toán con dựa trên kết quả đã tính toán trước đó. Hàm truy hồi được thiết lập sao cho nó tính toán kết quả tối ưu của bài toán con dựa trên các kết quả tối ưu của các bài toán con nhỏ hơn.

3. Các bước cập nhật bảng quy hoạch động: Để tính toán kết quả tối ưu của bài toán ban đầu, thuật toán quy hoạch động sẽ thực hiện các bước cập nhật bảng quy hoạch động. Các bước này bao gồm tính toán các kết quả tối ưu của các bài toán con, và cập nhật kết quả tối ưu của bài toán ban đầu dựa trên các kết quả tối ưu của các bài toán con nhỏ hơn.

4. Truy vết kết quả: Nếu cần, thuật toán quy hoạch động sẽ thực hiện truy vết để tìm ra phương án tối ưu của bài toán ban đầu từ bảng quy hoạch động.

Các phần này là các thành phần cơ bản của thuật toán quy hoạch động và có thể được sử dụng để giải quyết nhiều bài toán khác nhau. Tuy nhiên, cấu trúc chi tiết của thuật toán quy hoạch động có thể khác nhau tùy thuộc vào bài toán cụ thể.

Các phương pháp tối ưu hóa trong thuật toán quy hoạch động

Trong thuật toán quy hoạch động, có nhiều phương pháp tối ưu hóa khác nhau để tính toán kết quả tối ưu của bài toán. Dưới đây là một số phương pháp tối ưu hóa thường được sử dụng trong thuật toán quy hoạch động:

1. Cắt ngắn chiều dài của bảng quy hoạch động: Phương pháp này giúp giảm bớt thời gian và bộ nhớ cần thiết để tính toán kết quả tối ưu bằng cách loại bỏ các giá trị không cần thiết trong bảng quy hoạch động. Điều này có thể được thực hiện bằng cách giới hạn kích thước của bảng quy hoạch động hoặc chỉ tính toán một phần của bảng quy hoạch động.

2. Tối ưu hoá thứ tự tính toán: Phương pháp này giúp tối ưu hoá thứ tự tính toán các bài toán con để giảm bớt số lần tính toán trùng lặp và tăng tốc độ tính toán. Thông thường, các bài toán con nên được tính toán theo thứ tự từ nhỏ đến lớn để tối ưu hoá thời gian tính toán.

3. Sử dụng kỹ thuật tạm thời (memoization): Kỹ thuật tạm thời (memoization) là một phương pháp lưu trữ kết quả của các bài toán con đã tính toán để tránh tính toán lại trong quá trình tính toán kết quả tối ưu của bài toán lớn hơn. Kỹ thuật này giúp giảm thiểu số lần tính toán trùng lặp và tăng tốc độ tính toán.

4. Sử dụng kỹ thuật tối ưu hóa không gian đệ quy: Kỹ thuật tối ưu hóa không gian đệ quy giúp giảm bớt bộ nhớ cần thiết để tính toán kết quả tối ưu bằng cách sử dụng một ngăn xếp (stack) thay vì đệ quy để lưu trữ các kết quả của các bài toán con.

Những phương pháp tối ưu hóa này giúp cải thiện hiệu suất tính toán của thuật toán quy hoạch động và giúp tìm ra kết quả tối ưu của bài toán nhanh hơn và chính xác hơn.

Ví dụ minh họa

Các bài toán lý thuyết số về quy hoạch động (code ở cuối bài viết này)

Dướiđây là một số bài toán quy hoạch động về lý thuyết số:

1. Bài toán Số Fibonaci: Đưa ra số nguyên dương n, bài toán yêu cầu tìm số Fibonaci thứ n.

2. Bài toán Số Catalan: Bài toán yêu cầu tính số Catalan thứ n, với n là một số nguyên dương.

3. Bài toán Diophantine Equation: Bài toán yêu cầu tìm tất cả các cặp số nguyên dương (x, y) là nghiệm của phương trình ax + by = c, với a, b, c là các số nguyên cho trước.

4. Bài toán Số Mersenne: Bài toán yêu cầu tìm số nguyên tố Mersenne thứ n, với n là một số nguyên dương.

5. Bài toán Các số chính phương: Bài toán yêu cầu tính tổng của tất cả các số chính phương nhỏ hơn hoặc bằng n, với n là một số nguyên dương cho trước.

6. Bài toán Tích phân số: Bài toán yêu cầu tính giá trị của tích phân số đối với một hàm số cho trước.

7. Bài toán Số Harshad: Bài toán yêu cầu tìm tất cả các số Harshad nhỏ hơn hoặc bằng n, với n là một số nguyên dương cho trước. Một số Harshad là số tự nhiên chia hết cho tổng các chữ số của nó.

8. Bài toán Số Smith: Bài toán yêu cầu tìm tất cả các số Smith nhỏ hơn hoặc bằng n, với n là một số nguyên dương cho trước. Một số Smith là số tự nhiên mà tổng các chữ số của nó bằng tổng các chữ số của tất cả các thừa số nguyên tố của nó.

9. Bài toán Tổng số nguyên tố: Bài toán yêu cầu tính tổng của tất cả các số nguyên tố nhỏ hơn hoặc bằng n, với n là một số nguyên dương cho trước.

10. Bài toán Số dạng a^2 + b^2: Bài toán yêu cầu tìm số cách phân tích một số nguyên dương thành tổng của hai số bình phương, ví dụ như số 10 có thể phân tích thành 3^2 + 1^2 hoặc 2^2 + 2^2.

11. Bài toán Số dạng a^2 – b^2: Bài toán yêu cầu tìm số cách phân tích một số nguyên dương thành tích của hai số bình phương có hiệu là 1, ví dụ như số 15 có thể phân tích thành 4×4 – 1×1 hoặc 8×2 – 7×1.

Các bài toán này cũng đòi hỏi kiến thức lý thuyết số nâng cao và kỹ năng áp dụng thuật toán quy hoạch động để tối ưu hóa việc giải quyết các vấn đề lý thuyết số. Tuy nhiên, việc giải quyết các bài toán này sẽ giúp bạn nâng cao khả năng áp dụng thuật toán quy hoạch động trong lý thuyết số.

Ứng dụng của thuật toán quy hoạch động

Thuật toán quy hoạch động được ứng dụng rộng rãi trong các lĩnh vực khác nhau như:

1. Tối ưu hoá kinh doanh: Ví dụ như bài toán Knapsack mà chúng ta đã thảo luận ở trên, bài toán tối ưu vận chuyển hàng hóa, tối ưu quy hoạch sản xuất, tối ưu hoá mạng lưới cung ứng và nhiều bài toán tối ưu hóa khác trong lĩnh vực kinh doanh.

2. Lập trình động: Các thuật toán động quy hoạch được sử dụng để tìm kiếm đường đi ngắn nhất giữa các điểm trên bản đồ, giải quyết bài toán TSP (Travelling Salesman Problem) và các bài toán tối ưu hóa khác trong lĩnh vực lập trình động.

3. Trí tuệ nhân tạo: Thuật toán quy hoạch động được sử dụng trong các thuật toán trí tuệ nhân tạo như học máy và học sâu để giải quyết các bài toán tối ưu hóa khác nhau.

4. Công nghệ thông tin: Thuật toán quy hoạch động được sử dụng để giải quyết các bài toán tối ưu hóa trong các hệ thống quản lý tài nguyên và các hệ thống thông tin khác.

5. Khoa học dữ liệu: Thuật toán quy hoạch động được sử dụng để phân tích và xử lý dữ liệu, xác định các mẫu và xu hướng dữ liệu trong các ứng dụng khoa học dữ liệu.

Với những ứng dụng rộng rãi như vậy, thuật toán quy hoạch động là một trong những công cụ quan trọng để giải quyết các bài toán tối ưu hóa và giúp các nhà nghiên cứu, nhà kinh doanh, nhà phát triển phần mềm và các chuyên gia dữ liệu có thể tối ưu hóa các quy trình và thuận tiện trong việc ra quyết định.

Đánh giá

Thuật toán quy hoạch động là một kỹ thuật giải quyết các vấn đề tối ưu hoá, thông qua việc chia nhỏ vấn đề ban đầu thành các bài toán con nhỏ hơn và lưu trữ lại kết quả tính toán các bài toán con đó để giải quyết các bài toán lớn hơn. Thuật toán quy hoạch động có thể được áp dụng để giải quyết các vấn đề như tìm kiếm đường đi ngắn nhất trong đồ thị, tối ưu hóa phân chia gói hàng, tìm cách phân tích một số thành tổng các số khác, và nhiều vấn đề khác nữa.

Ưu điểm:

• Đảm bảo tìm kiếm được giải pháp tối ưu cho các vấn đề tối ưu hóa.
• Giải quyết được các vấn đề phức tạp với độ phức tạp tính toán thấp hơn so với các phương pháp tìm kiếm giải pháp khác.
• Có khả năng tìm được nghiệm tối ưu dựa trên các giá trị đã tính toán được trong quá trình giải quyết các bài toán con.

Nhược điểm:

• Cần phải biết chính xác vấn đề cần giải quyết và định nghĩa các bài toán con phù hợp để lưu trữ lại kết quả tính toán.
• Đôi khi không thể tìm được nghiệm tối ưu nếu vấn đề ban đầu không đáp ứng được các giả định để áp dụng thuật toán quy hoạch động.

Code một số bài toán lý thuyết số về Quy hoạch động

Bài toán Số Fibonaci

Đưa ra số nguyên dương n, bài toán yêu cầu tìm số Fibonaci thứ n. 

#include <iostream>
using namespace std;

int fib(int n)
{
    int f[n + 1];
    f[0] = 0, f[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i - 2];
    }

    return f[n];
}

int main()
{
    int n = 10;
    cout << "Fibonacci number at position " << n << " is " << fib(n) << endl;
    return 0;
}

Giải thích:

• Hàm fib() được sử dụng để tính toán số Fibonaci thứ n.
• Mảng f được sử dụng để lưu trữ các số Fibonaci tính toán được, bắt đầu từ f[0] và f[1].
• Vòng lặp for sử dụng phương pháp quy hoạch động để tính toán số Fibonaci cho các vị trí tiếp theo, dựa trên các giá trị đã tính toán trước đó.
• Hàm main() chỉ đơn giản là gọi hàm fib() và in kết quả ra màn hình.

Ví dụ trên sẽ tính toán và in ra số Fibonaci thứ 10, tuy nhiên, giá trị này có thể được thay đổi bằng cách thay đổi giá trị biến n trong hàm main().

Bài toán Số Catalan

Bài toán yêu cầu tính số Catalan thứ n, với n là một số nguyên dương

#include <iostream>
using namespace std;

unsigned long int catalan(int n)
{
    unsigned long int catalan[n + 1];
    catalan[0] = catalan[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        catalan[i] = 0;
        for (int j = 0; j < i; j++)
        {
            catalan[i] += catalan[j] * catalan[i - j - 1];
        }
    }

    return catalan[n];
}

int main()
{
    int n = 10;
    cout << "Catalan number at position " << n << " is " << catalan(n) << endl;
    return 0;
}

Giải thích:

• Hàm catalan() được sử dụng để tính toán số Catalan thứ n.
• Mảng catalan được sử dụng để lưu trữ các giá trị của số Catalan, bắt đầu từ catalan[0] và catalan[1].
• Vòng lặp for sử dụng phương pháp quy hoạch động để tính toán số Catalan cho các vị trí tiếp theo, dựa trên các giá trị đã tính toán trước đó.
• Hàm main() chỉ đơn giản là gọi hàm catalan() và in kết quả ra màn hình.

Ví dụ trên sẽ tính toán và in ra số Catalan thứ 10, tuy nhiên, giá trị này có thể được thay đổi bằng cách thay đổi giá trị biến n trong hàm main().

Bài toán Diophantine Equation

Bài toán yêu cầu tìm tất cả các cặp số nguyên dương (x, y) là nghiệm của phương trình ax + by = c, với a, b, c là các số nguyên cho trước.

Để giải bài toán Diophantine Equation, chúng ta có thể sử dụng phương pháp mở rộng Euclid (Extended Euclidean Algorithm) để tìm ra nghiệm (x’, y’) của phương trình diofantin ax + by = gcd(a, b), sau đó áp dụng công thức x = x’ * c / gcd(a, b) và y = y’ * c / gcd(a, b) để tìm ra các cặp số (x, y) là nghiệm của phương trình ban đầu.

#include <iostream>

using namespace std;

int gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

void solve_diophantine(int a, int b, int c) {
    int x, y;
    int d = gcd(a, b, x, y);
    if (c % d != 0) {
        cout << "No solution" << endl;
        return;
    }
    int k = c / d;
    x *= k;
    y *= k;
    cout << "One solution: (" << x << ", " << y << ")" << endl;
    int x0 = x + b / d;
    int y0 = y - a / d;
    cout << "Another solution: (" << x0 << ", " << y0 << ")" << endl;
}

int main() {
    int a, b, c;
    cout << "Enter coefficients a, b, and c: ";
    cin >> a >> b >> c;
    solve_diophantine(a, b, c);
    return 0;
}

Trong code trên, hàm gcd được sử dụng để tính toán GCD và nghiệm của phương trình diofantin ax + by = gcd(a, b), và hàm solve_diophantine được sử dụng để giải phương trình ax + by = c. Nếu không tồn tại nghiệm thì hàm sẽ in ra thông báo “No solution”. Nếu tồn tại ít nhất một nghiệm, hàm sẽ in ra hai giá trị là một nghiệm và một nghiệm khác của phương trình.

Bài toán Số Mersenne

Bài toán yêu cầu tìm số nguyên tố Mersenne thứ n, với n là một số nguyên dương.

Để giải bài toán Số Mersenne bằng thuật toán quy hoạch động, ta có thể sử dụng công thức sau để kiểm tra xem một số nguyên dương p có phải là số nguyên tố Mersenne hay không:

M_p = 2^p – 1 là số nguyên tố Mersenne khi và chỉ khi tồn tại số nguyên tố q sao cho p = 2^q – 1.

Với công thức này, ta có thể kiểm tra từng số nguyên tố p để tìm số nguyên tố Mersenne thứ n.

#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

vector<int> findMersenne(int n) {
    vector<int> result;
    int count = 0, p = 2;
    while (count < n) {
        int q = 1;
        while (!isPrime(q)) {
            q++;
        }
        int m = (1 << q) - 1;
        if (isPrime(m)) {
            result.push_back(m);
            count++;
        }
        p++;
    }
    return result;
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;
    vector<int> mersennes = findMersenne(n);
    cout << "Cac so nguyen to Mersenne tu 1 den " << n << " la: ";
    for (int i = 0; i < mersennes.size(); i++) {
        cout << mersennes[i] << " ";
    }
    cout << endl;
    return 0;
}

Trong đó, hàm isPrime(n) được sử dụng để kiểm tra xem một số nguyên dương n có phải là số nguyên tố hay không. Hàm findMersenne(n) tìm và trả về n số nguyên tố Mersenne đầu tiên. Ta sử dụng hai biến đếm count và p để lần lượt đếm số nguyên tố Mersenne và kiểm tra các số nguyên tố q. Vòng lặp trong hàm findMersenne(n) được sử dụng để tìm các số nguyên tố Mersenne đến khi đủ n số.

Bài toán Các số chính phương

Bài toán yêu cầu tính tổng của tất cả các số chính phương nhỏ hơn hoặc bằng n, với n là một số nguyên dương cho trước.

Để giải bài toán này bằng thuật toán Quy hoạch động, ta có thể sử dụng một mảng 1 chiều để lưu trữ các giá trị tổng các số chính phương từ 0 đến i, với i là chỉ số của phần tử trong mảng.

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int dp[n + 1]; // Khởi tạo mảng dp để lưu trữ các kết quả phần tử tương ứng
    dp[0] = 0; // Khởi tạo giá trị cho phần tử đầu tiên
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + sqrt(i); // Tính giá trị của phần tử thứ i dựa trên phần tử trước đó và căn bậc hai của i
    }

    cout << dp[n] << endl; // In kết quả

    return 0;
}

Bài toán Tích phân số

Bài toán yêu cầu tính giá trị của tích phân số đối với một hàm số cho trước.

Để giải bài toán tích phân số, ta có thể sử dụng phương pháp Quy hoạch động với cách tiếp cận tương tự như việc tính toán giá trị của phương trình đệ quy trong ví dụ về bài toán số Fibonacci.

Cụ thể, ta có thể chia đề bài thành các bước như sau:

1. Xác định khoảng cách chia nhỏ của phân vùng.
2. Tính toán giá trị hàm số tại các điểm chia nhỏ này.
3. Tính tổng các giá trị hàm số tại các điểm chia nhỏ này.
4. Nhân kết quả với độ dài của mỗi phân vùng.

#include <iostream>
using namespace std;

// Hàm tính giá trị của hàm số f(x)
double f(double x)
{
    return x * x;
}

// Hàm tính giá trị của tích phân số bằng phương pháp Quy hoạch động
double integrate(double a, double b, int n)
{
    double h = (b - a) / n;
    double res = 0.0;

    // Tính giá trị của hàm số tại các điểm chia nhỏ của khoảng [a, b]
    for (int i = 0; i <= n; i++)
    {
        double x = a + i * h;
        res += f(x);
    }

    // Nhân tổng các giá trị hàm số tại các điểm chia nhỏ với độ dài của mỗi phân vùng
    res *= h;

    return res;
}

int main()
{
    double a = 0.0, b = 1.0;
    int n = 1000;

    double res = integrate(a, b, n);

    cout << "Gia tri cua tich phan f(x) tu " << a << " den " << b << " voi " << n << " phan vung la: " << res << endl;

    return 0;
}

Trong đoạn mã trên, hàm f(x) được sử dụng để tính giá trị của hàm số tại mỗi điểm chia nhỏ trong khoảng [a, b]. Hàm integrate(a, b, n) sẽ tính tổng các giá trị hàm số tại các điểm chia nhỏ, nhân kết quả với độ dài của mỗi phân vùng và trả về giá trị tích phân số.

Kết quả trả về sẽ được in ra màn hình.

Bài toán Số Harshad

Bài toán yêu cầu tìm tất cả các số Harshad nhỏ hơn hoặc bằng n, với n là một số nguyên dương cho trước. Một số Harshad là số tự nhiên chia hết cho tổng các chữ số của nó.

Để giải bài toán Số Harshad bằng thuật toán quy hoạch động, ta có thể sử dụng các bước sau:

• Khởi tạo mảng dp với dp[i] là true nếu số i là số Harshad, và false nếu không phải.
• Tính tổng các chữ số của mỗi số trong khoảng từ 1 đến n, và kiểm tra xem số đó có chia hết cho tổng chữ số đó hay không. Nếu có, đánh dấu số đó là số Harshad.
• Tính tổng các chữ số của mỗi số Harshad và kiểm tra xem kết quả có phải là số Harshad hay không. Nếu đúng, đánh dấu số đó là số Harshad mở rộng (extended Harshad).
• Từ các số Harshad mở rộng, ta có thể tính được tất cả các số Harshad khác bằng cách thêm một chữ số vào cuối của số Harshad mở rộng đó.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int i = 1; i <= n; i++) {
        int sum = 0;
        int temp = i;
        while (temp > 0) {
            sum += temp % 10;
            temp /= 10;
        }
        if (i % sum == 0) {
            dp[i] = true;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dp[i]) {
            int sum = 0;
            int temp = i;
            while (temp > 0) {
                sum += temp % 10;
                temp /= 10;
            }
            if (dp[sum]) {
                cout << i << " ";
            }
        }
    }
    return 0;
}

Giải thích code:

• Dòng 5: Nhập vào số nguyên dương n.
• Dòng 7-8: Khởi tạo mảng dp và đánh dấu dp[0] là true.
• Dòng 10-15: Duyệt từng số trong khoảng từ 1 đến n, tính tổng chữ số và kiểm tra xem số đó có chia hết cho tổng chữ số hay không. Nếu có, đánh dấu dp[i] là true.
• Dòng 17-22: Duyệt từng số Harshad, tính tổng chữ số và kiểm tra xem kết quả có phải là số Harshad hay không. Nếu đúng, in ra số đó.
• Dòng 24: Kết thúc chương trình.

Bài toán Số Smith

Bài toán yêu cầu tìm tất cả các số Smith nhỏ hơn hoặc bằng n, với n là một số nguyên dương cho trước. Một số Smith là số tự nhiên mà tổng các chữ số của nó bằng tổng các chữ số của tất cả các thừa số nguyên tố của nó.

Để giải bài toán Số Smith, ta sử dụng thuật toán quy hoạch động để kiểm tra xem một số có phải là số Smith hay không.

Cụ thể, để kiểm tra một số có phải là số Smith, ta thực hiện các bước sau:

1. Tính tổng các chữ số của số đó.
2. Tìm tất cả các thừa số nguyên tố của số đó.
3. Tính tổng các chữ số của tất cả các thừa số nguyên tố của số đó.
4. Kiểm tra xem tổng các chữ số ở bước 1 có bằng tổng các chữ số ở bước 3 hay không.

Nếu tổng các chữ số ở bước 1 bằng tổng các chữ số ở bước 3, thì số đó là số Smith.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Hàm tính tổng các chữ số của một số nguyên
int sumOfDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

// Hàm phân tích thừa số nguyên tố và tính tổng các chữ số của nó
int sumOfPrimeFactors(int n) {
    int sum = 0;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            sum += sumOfDigits(i);
            n /= i;
        }
    }
    if (n > 1) {
        sum += sumOfDigits(n);
    }
    return sum;
}

// Hàm kiểm tra số Smith
bool isSmith(int n) {
    int sumOfDigitsN = sumOfDigits(n);
    int sumOfDigitsPrimeFactors = sumOfPrimeFactors(n);
    return (sumOfDigitsN == sumOfDigitsPrimeFactors);
}

// Hàm tìm các số Smith nhỏ hơn hoặc bằng n
vector<int> findSmithNumbers(int n) {
    vector<int> smithNumbers;
    for (int i = 1; i <= n; i++) {
        if (isSmith(i)) {
            smithNumbers.push_back(i);
        }
    }
    return smithNumbers;
}

// Hàm in ra các số Smith
void printSmithNumbers(vector<int> smithNumbers) {
    if (smithNumbers.empty()) {
        cout << "Khong co so Smith nao trong khoang nay!" << endl;
    } else {
        cout << "Cac so Smith la: ";
        for (int i = 0; i < smithNumbers.size(); i++) {
            cout << smithNumbers[i] << " ";
        }
        cout << endl;
    }
}

// Hàm main
int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;
    vector<int> smithNumbers = findSmithNumbers(n);
    printSmithNumbers(smithNumbers);
    return 0;
}

Bài toán Tổng số nguyên tố

Bài toán yêu cầu tính tổng của tất cả các số nguyên tố nhỏ hơn hoặc bằng n, với n là một số nguyên dương cho trước.

Để giải bài toán Tổng số nguyên tố bằng thuật toán quy hoạch động, ta có thể sử dụng một mảng đánh dấu để lưu trữ thông tin về tính nguyên tố của từng số nguyên dương nhỏ hơn hoặc bằng n. Ban đầu, ta khởi tạo tất cả các phần tử trong mảng đánh dấu đều là true. Sau đó, ta duyệt từng số nguyên dương từ 2 đến n, và đánh dấu tất cả các bội số của số đó là false trong mảng đánh dấu. Cuối cùng, ta tính tổng của tất cả các số nguyên tố bằng cách duyệt lại mảng đánh dấu và cộng các số nguyên tố lại với nhau.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    // Khởi tạo mảng đánh dấu
    vector<bool> is_prime(n + 1, true);

    // Duyệt từng số nguyên dương từ 2 đến n
    for (int i = 2; i <= n; i++) {
        // Nếu i là số nguyên tố, đánh dấu các bội số của i là false
        if (is_prime[i]) {
            for (int j = 2 * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // Tính tổng của tất cả các số nguyên tố nhỏ hơn hoặc bằng n
    int sum = 0;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            sum += i;
        }
    }

    // In ra kết quả
    cout << sum << endl;

    return 0;
}

Trong đoạn code trên, ta sử dụng một vector có kích thước là n + 1 để lưu trữ thông tin về tính nguyên tố của từng số nguyên dương nhỏ hơn hoặc bằng n. Ban đầu, ta khởi tạo tất cả các phần tử trong vector đều là true. Sau đó, ta duyệt từng số nguyên dương từ 2 đến n, và đánh dấu tất cả các bội số của số đó là false trong vector. Cuối cùng, ta tính tổng của tất cả các số nguyên tố bằng cách duyệt lại vector và cộng các số nguyên tố lại với nhau.

Bài toán Số dạng a^2 + b^2

Bài toán yêu cầu tìm số cách phân tích một số nguyên dương thành tổng của hai số bình phương, ví dụ như số 10 có thể phân tích thành 3^2 + 1^2 hoặc 2^2 + 2^2.

Để giải bài toán này bằng thuật toán quy hoạch động, ta có thể sử dụng một mảng dp, trong đó phần tử thứ i của mảng sẽ là số cách phân tích i thành tổng của hai số bình phương.

Để tính dp[i], ta có thể duyệt các số j từ 0 đến sqrt(i) và tính dp[i – j*j]. Sau đó, ta cộng các giá trị này lại để tính dp[i].

Với mỗi i, ta cũng có thể duyệt lại các giá trị dp[jj + k], với k < i – jj, để tính tổng số cách phân tích i thành tổng của hai số bình phương.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;

    int dp[n+1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = 0;
        for (int j = 1; j <= sqrt(i); j++) {
            dp[i] += dp[i - j*j];
        }
    }

    cout << dp[n];
    return 0;
}

Bài toán Số dạng a^2 – b^2

Bài toán yêu cầu tìm số cách phân tích một số nguyên dương thành tích của hai số bình phương có hiệu là 1, ví dụ như số 15 có thể phân tích thành 4×4 – 1×1 hoặc 8×2 – 7×1.

S(n) = S(n-2) + [(n-1) / 2] Trong đó, S(n) là số cách phân tích số n thành tích của hai số bình phương có hiệu là 1.

Với công thức trên, ta có thể tính được số cách phân tích của tất cả các số từ 1 đến n. Bước đầu tiên, ta khởi tạo một mảng DP với DP[i] là số cách phân tích i thành tích của hai số bình phương có hiệu là 1. Sau đó, ta duyệt từng số từ 3 đến n, áp dụng công thức trên để tính giá trị DP[i].

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> dp(n + 1);

    dp[0] = dp[1] = 0;
    dp[2] = 1;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 2] + ((i - 1) / 2);
    }

    cout << "So cach phan tich " << n << " thanh tich hai so binh phuong co hieu la 1 la: " << dp[n] << endl;

    return 0;
}

Với đoạn code trên, sau khi nhập giá trị n từ người dùng, ta sử dụng một mảng vector dp để tính số cách phân tích của các số từ 0 đến n. Ban đầu, ta gán dp[0] và dp[1] là 0, và dp[2] là 1 (trường hợp đặc biệt). Sau đó, ta duyệt từng số i từ 3 đến n, và tính giá trị dp[i] bằng cách áp dụng công thức S(n) = S(n-2) + [(n-1) / 2]. Cuối cùng, ta in ra kết quả tìm được.

Chạy chương trình và nhập vào một số nguyên dương n, ta sẽ nhận được kết quả số cách phân tích n thành tích của hai số bình phương có hiệu là 1.

Kết luận

Trên đây là một số nội dung cơ bản về thuật toán quy hoạch động. Hy vọng bài viết sẽ là hữu ích đối với các bạn./.