Thuật toán quay lui
Dưới đây là một ví dụ về cách xếp ba lô trong C# sử dụng giải thuật quay lui (backtracking):
using System;
class Knapsack
{
static int[] weights = {2, 3, 5, 7};
static int[] values = {1, 5, 2, 4};
static int capacity = 10;
static int[] bestSolution;
static int bestValue;
static void Main()
{
int[] currentSolution = new int[weights.Length];
bestSolution = new int[weights.Length];
KnapsackRecursive(0, currentSolution, 0, 0);
Console.WriteLine("Best solution:");
for (int i = 0; i < bestSolution.Length; i++)
{
Console.WriteLine("{0}: {1}", i, bestSolution[i]);
}
Console.WriteLine("Total value: {0}", bestValue);
}
static void KnapsackRecursive(int index, int[] currentSolution, int currentValue, int currentWeight)
{
if (index == weights.Length)
{
if (currentValue > bestValue)
{
bestValue = currentValue;
Array.Copy(currentSolution, bestSolution, currentSolution.Length);
}
return;
}
if (currentWeight + weights[index] <= capacity)
{
currentSolution[index] = 1;
KnapsackRecursive(index + 1, currentSolution, currentValue + values[index], currentWeight + weights[index]);
}
currentSolution[index] = 0;
KnapsackRecursive(index + 1, currentSolution, currentValue, currentWeight);
}
}
Trong ví dụ này, chúng ta có một mảng weights chứa trọng lượng của các vật phẩm, một mảng values chứa giá trị của các vật phẩm, và một giới hạn trọng lượng capacity cho phép trong ba lô. Giải thuật quay lui được sử dụng để tìm kiếm tất cả các cách xếp ba lô có thể và tìm ra giải pháp tốt nhất.
Hàm KnapsackRecursive nhận vào một chỉ số index, một mảng currentSolution chứa giá trị 0 hoặc 1 để biểu diễn xem vật phẩm ở chỉ số index có được chọn hay không, một giá trị currentValue biểu thị giá trị hiện tại của các vật phẩm được chọn, và một giá trị currentWeight biểu thị trọng lượng hiện tại của các vật phẩm được chọn.
Nếu index bằng độ dài của mảng weights, chúng ta đã thử hết tất cả các cách xếp ba lô. Nếu currentValue lớn hơn giá trị tốt nhất hiện tại (bestValue), chúng ta cập nhật giá trị tốt nhất và sao chép mảng currentSolution vào mảng bestSolution.
Nếu vật phẩm ở chỉ số index có thể được chọn và không vượt quá giới hạn trọng lượng của ba lô (currentWeight + weights[index] <= capacity), chúng ta đánh dấu vật phẩm đó bằng 1 trong mảng currentSolution, tăng giá trị currentValue bằng giá trị của vật phẩm đó, tăng currentWeight bằng trọng lượng của vật phẩm đó và tiếp tục đệ quy đến vật phẩm tiếp theo (index + 1).
Nếu vật phẩm ở chỉ số index không được chọn, chúng ta đánh dấu vật phẩm đó bằng 0 trong mảng currentSolution và tiếp tục đệ quy đến vật phẩm tiếp theo (index + 1).
Cuối cùng, trong hàm Main, chúng ta gọi hàm KnapsackRecursive với index ban đầu bằng 0, currentSolution ban đầu là một mảng trống, currentValue ban đầu là 0 và currentWeight ban đầu là 0 để bắt đầu quá trình tìm kiếm. Sau khi tìm kiếm hoàn tất, chúng ta in ra giải pháp tốt nhất và giá trị tương ứng.
Lưu ý rằng ví dụ này sử dụng các giá trị cố định cho mảng weights, mảng values và giới hạn trọng lượng capacity. Để giải quyết các trường hợp khác nhau, bạn có thể sửa đổi giá trị này để phù hợp với yêu cầu của bài toán.
Thuật toán quy hoạch động
Dưới đây là một ví dụ về cách giải bài toán xếp ba lô bằng thuật toán Quy hoạch động trong C#:
using System;
class Knapsack
{
static int[] weights = {2, 3, 5, 7};
static int[] values = {1, 5, 2, 4};
static int capacity = 10;
static void Main()
{
int[,] table = new int[weights.Length + 1, capacity + 1];
for (int i = 0; i <= weights.Length; i++)
{
for (int j = 0; j <= capacity; j++)
{
if (i == 0 || j == 0)
{
table[i, j] = 0;
}
else if (weights[i - 1] <= j)
{
table[i, j] = Math.Max(values[i - 1] + table[i - 1, j - weights[i - 1]], table[i - 1, j]);
}
else
{
table[i, j] = table[i - 1, j];
}
}
}
Console.WriteLine("Best value: {0}", table[weights.Length, capacity]);
int[] solution = new int[weights.Length];
for (int i = weights.Length, j = capacity; i > 0 && j > 0; i--)
{
if (table[i, j] != table[i - 1, j])
{
solution[i - 1] = 1;
j -= weights[i - 1];
}
}
Console.WriteLine("Solution:");
for (int i = 0; i < solution.Length; i++)
{
Console.WriteLine("{0}: {1}", i, solution[i]);
}
}
}
Trong ví dụ này, chúng ta sử dụng một mảng 2 chiều table để lưu giữ giá trị tối ưu cho mỗi trọng lượng và số lượng vật phẩm đã xét. Đầu tiên, chúng ta khởi tạo table với giá trị 0 cho trọng lượng 0 và số lượng vật phẩm 0.
Sau đó, chúng ta sử dụng hai vòng lặp để tính toán giá trị tối ưu cho tất cả các trọng lượng và số lượng vật phẩm. Với mỗi vật phẩm, chúng ta kiểm tra xem nếu trọng lượng vật phẩm đó nhỏ hơn hoặc bằng trọng lượng đang xét, chúng ta có thể chọn vật phẩm đó hoặc không chọn vật phẩm đó để tối đa hóa giá trị. Nếu trọng lượng vật phẩm đó lớn hơn trọng lượng đang xét, chúng ta không thể chọn vật phẩm đó và giá trị tối ưu tiếp tục giữ nguyên.
Cuối cùng, chúng ta in ra giá trị tối ưu và cách xếp ba lô tương ứng. Để tìm cách xếp ba lô tương ứng, chúng ta sử dụng một mảng solution để lưu trữ trạng thái (có chọn hay không chọn) của mỗi vật phẩm. Chúng ta duyệt table theo chiều ngược lại để xác định xem mỗi vật phẩm có được chọn hay không. Nếu giá trị tối ưu của trọng lượng và số lượng vật phẩm đã xét tại vị trí (i, j) khác với giá trị tối ưu của trọng lượng và số lượng vật phẩm đã xét tại vị trí (i - 1, j), chúng ta chọn vật phẩm đó và giảm trọng lượng đang xét bằng trọng lượng của vật phẩm đó.
Lưu ý rằng trong ví dụ này, chúng ta sử dụng các giá trị cố định cho mảng weights, mảng values và giới hạn trọng lượng capacity. Để giải quyết các trường hợp khác nhau, bạn có thể sửa đổi giá trị này để phù hợp với yêu cầu của bài toán.