Giải thuật Knapsack bằng Quy hoạch Động trong C#

Bài toán knapsack (bài toán cái túi) là một trong những bài toán tối ưu hóa nổi tiếng trong khoa học máy tính. Bài toán này yêu cầu chọn một tập hợp con của các đồ vật có trọng lượng và giá trị khác nhau sao cho tổng trọng lượng không vượt quá một giới hạn nhất định và tổng giá trị là lớn nhất có thể.

Đề bài

Cho một danh sách các đồ vật, mỗi đồ vật có trọng lượng và giá trị. Bạn có một cái túi có thể chứa tối đa một trọng lượng nhất định. Hãy tìm cách chọn đồ vật để tối đa hóa giá trị trong khi tổng trọng lượng không vượt quá giới hạn.

Thuật toán Quy hoạch Động

Chúng ta sẽ sử dụng một bảng 2D để lưu trữ các giá trị tối ưu của bài toán con. Giả sử dp[i][w] là giá trị tối đa có thể đạt được với các đồ vật từ 1 đến i và trọng lượng tối đa là w.

dp[i][w] = dp[i-1][w] nếu đồ vật thứ i không được chọn.
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) nếu đồ vật thứ i được chọn.

Mã C# cho Thuật toán Knapsack

Dưới đây là mã C# để giải quyết bài toán knapsack bằng phương pháp quy hoạch động:

using System;

class Knapsack
{
    // Hàm giải bài toán Knapsack
    public static int KnapsackDP(int[] weights, int[] values, int capacity)
    {
        int n = weights.Length;
        int[,] dp = new int[n + 1, capacity + 1];

        // Lặp qua các đồ vật
        for (int i = 1; i <= n; i++)
        {
            // Lặp qua các mức trọng lượng từ 0 đến capacity
            for (int w = 0; w <= capacity; w++)
            {
                // Nếu trọng lượng của đồ vật lớn hơn trọng lượng hiện tại w, không chọn đồ vật này
                if (weights[i - 1] > w)
                {
                    dp[i, w] = dp[i - 1, w];
                }
                else
                {
                    // Chọn giá trị tối ưu giữa việc chọn hoặc không chọn đồ vật này
                    dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weights[i - 1]] + values[i - 1]);
                }
            }
        }

        // Giá trị tối đa của bài toán Knapsack
        return dp[n, capacity];
    }

    public static void Main()
    {
        int[] weights = { 1, 3, 4, 5 };
        int[] values = { 1, 4, 5, 7 };
        int capacity = 7;

        int maxVal = KnapsackDP(weights, values, capacity);
        Console.WriteLine("Giá trị tối đa có thể đạt được: " + maxVal);
    }
}

Giải thích mã

Khởi tạo bảng dp:
- dp[i, w] là giá trị tối đa có thể đạt được với i đồ vật đầu tiên và trọng lượng tối đa là w.
Lặp qua các đồ vật:
- Với mỗi đồ vật, ta xét tất cả các trọng lượng từ 0 đến capacity.
Cập nhật bảng dp:
- Nếu trọng lượng của đồ vật hiện tại lớn hơn trọng lượng đang xét (w), ta không thể chọn đồ vật này, nên giá trị tại dp[i, w] sẽ bằng giá trị tại dp[i-1, w].
- Nếu có thể chọn đồ vật, ta cập nhật dp[i, w] bằng giá trị lớn hơn giữa việc chọn hoặc không chọn đồ vật này.
Kết quả:
- Giá trị tối đa có thể đạt được với tất cả các đồ vật và trọng lượng tối đa là dp[n, capacity].

Kết luận

Bài toán knapsack là một bài toán tối ưu hóa điển hình có thể giải quyết hiệu quả bằng phương pháp quy hoạch động. Mã C# ở trên minh họa cách áp dụng phương pháp này để tìm giá trị tối ưu của knapsack với trọng lượng và giá trị của các đồ vật cho trước.

Đăng ký

Giải thuật Knapsack bằng Quy hoạch Động trong C#