Bài toán về chiếc ba lô phân số: Thuật toán tham lam với ví dụ
Sarah Chen
Chiến lược tham lam là gì?
Thuật toán tham lam giống như thuật toán quy hoạch động thường được sử dụng để giải các bài toán tối ưu (tìm lời giải tốt nhất của bài toán theo một tiêu chí cụ thể).
Thuật toán tham lam triển khai các lựa chọn cục bộ tối ưu với hy vọng rằng các lựa chọn đó sẽ dẫn đến một giải pháp toàn cục tối ưu cho vấn đề cần giải quyết. Thuật toán tham lam thường không quá khó để thiết lập, nhanh chóng (độ phức tạp thời gian thường là một hàm tuyến tính hoặc rất giống một hàm bậc hai). Bên cạnh đó, các chương trình này không khó để gỡ lỗi và sử dụng ít bộ nhớ hơn. Nhưng kết quả không phải lúc nào cũng là một giải pháp tối ưu.
Chiến lược tham lam thường được sử dụng để giải bài toán tối ưu tổ hợp bằng cách xây dựng phương án A. Phương án A được xây dựng bằng cách chọn từng thành phần Ai của A cho đến khi hoàn thành (đủ n thành phần). Với mỗi Ai, bạn chọn Ai một cách tối ưu. Bằng cách này, có thể ở bước cuối cùng bạn không có gì để chọn ngoài việc chấp nhận giá trị còn lại cuối cùng.
Có hai thành phần quan trọng của các quyết định tham lam:
- Cách lựa chọn tham lam. Bạn có thể chọn giải pháp nào là tốt nhất hiện tại và sau đó giải quyết vấn đề con phát sinh từ việc thực hiện lựa chọn cuối cùng. Việc lựa chọn thuật toán tham lam có thể phụ thuộc vào các lựa chọn trước đó. Nhưng nó không thể phụ thuộc vào bất kỳ lựa chọn nào trong tương lai hoặc phụ thuộc vào lời giải của các bài toán con. Thuật toán phát triển theo cách thực hiện các phép chọn theo vòng lặp, đồng thời thu gọn bài toán đã cho thành các bài toán con nhỏ hơn.
- Cấu trúc nền tối ưu. Bạn thực hiện cấu trúc con tối ưu cho một bài toán nếu giải pháp tối ưu của bài toán này chứa các giải pháp tối ưu cho các bài toán con của nó.
Thuật toán tham lam có năm thành phần:
- Một tập hợp các ứng cử viên, từ đó tạo ra các giải pháp.
- Một chức năng lựa chọn, để chọn ra ứng cử viên tốt nhất để thêm vào giải pháp.
- Hàm khả thi được sử dụng để quyết định xem có thể sử dụng một ứng cử viên để xây dựng giải pháp hay không.
- Hàm mục tiêu, cố định giá trị của lời giải hoặc lời giải không đầy đủ.
- Một chức năng đánh giá, cho biết khi nào bạn tìm thấy một giải pháp hoàn chỉnh.
Ý tưởng của kẻ tham lam
Với ý tưởng đầu tiên, bạn có các bước sau của Greedy One:
- Sắp xếp theo thứ tự giá trị không tăng dần.
- Lần lượt xem xét các kiện hàng đã đặt, cho kiện hàng đang xem xét vào ba lô nếu thể tích còn lại của ba lô đủ chứa gói hàng đó (nghĩa là tổng trọng lượng các kiện hàng đã cho vào ba lô và trọng lượng của các kiện hàng đang xem xét không vượt quá sức chứa của ba lô).
Tuy nhiên, thuật toán tham lam này không phải lúc nào cũng đưa ra giải pháp tối ưu. Ở đây bạn có một phản ví dụ:
- Các tham số của bài toán là: n = 3; M = 19.
- Các gói: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Giá trị lớn nhưng cũng có trọng lượng lớn.
- Thuật toán sẽ chọn gói 1 có tổng giá trị là 20, đồng thời chọn giải pháp tối ưu của bài toán (gói 2, gói 3) có tổng giá trị là 24.
Ý tưởng của Greedy Two
Với ý tưởng thứ hai, bạn có các bước sau của Greedy Two:
- Sắp xếp theo thứ tự trọng số không giảm.
- Lần lượt xem xét các kiện hàng đã đặt, cho kiện hàng đang xem xét vào ba lô nếu thể tích còn lại của ba lô đủ chứa gói hàng đó (nghĩa là tổng trọng lượng các kiện hàng đã cho vào ba lô và trọng lượng của các kiện hàng đang xem xét không vượt quá sức chứa của ba lô).
Tuy nhiên, thuật toán tham lam này không phải lúc nào cũng đưa ra giải pháp tối ưu. Ở đây bạn có một phản ví dụ:
- Các tham số của bài toán là: n = 3; M = 11.
- Các gói: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Trọng lượng nhẹ nhưng giá trị cũng rất nhẹ.
- Thuật toán sẽ chọn (gói 1, gói 2) có tổng giá trị là 26, còn phương án tối ưu của bài toán là (gói 3) có tổng giá trị là 28.
Ý tưởng của Greedy Three
Với ý tưởng thứ ba, bạn có các bước sau của Greedy Three. Trên thực tế, đây là thuật toán được sử dụng rộng rãi nhất.
- Sắp xếp các gói hàng theo thứ tự không tăng giá trị đơn giá
. Bạn có:
- Lần lượt xem xét các kiện hàng đã đặt, cho kiện hàng đang xem xét vào ba lô nếu thể tích còn lại của ba lô đủ chứa gói hàng đó (nghĩa là tổng trọng lượng các kiện hàng đã cho vào ba lô và trọng lượng của các kiện hàng đang xem xét không vượt quá sức chứa của ba lô).
Ý tưởng: Ý tưởng tham lam của bài toán đó là tính toán 
tỷ lệ của mỗi 
. Sau đó sắp xếp các tỷ lệ này theo thứ tự giảm dần. Bạn sẽ chọn mức cao nhất gói hàng và dung tích của ba lô có thể chứa gói hàng đó (còn lại > wi). Mỗi lần cho một gói hàng vào ba lô cũng sẽ làm giảm sức chứa của ba lô.
Cách chọn gói:
- Hãy xem xét mảng chi phí đơn vị. Bạn chọn các gói theo đơn giá giảm dần.
- Giả sử bạn tìm được một phần lời giải: (x1,…, Xi).
- Giá trị của chiếc ba lô thu được:
- Tương ứng với trọng lượng của kiện hàng đã cho vào ba lô:
- Do đó giới hạn trọng lượng còn lại của ba lô là:
Các bước của thuật toán
Bạn thấy đây là vấn đề tìm kiếm max. Danh sách các gói được sắp xếp theo thứ tự đơn giá giảm dần để xem xét phân nhánh.
- Bước 1: Nút gốc thể hiện trạng thái ban đầu của ba lô, nơi bạn chưa chọn bất kỳ gói nào.
- Tổng giá trị = 0.
- Giới hạn trên của nút gốc UpperBound = M * Đơn giá tối đa.
- Bước 2: Nút gốc sẽ có các nút con tương ứng với khả năng lựa chọn gói có đơn giá lớn nhất. Với mỗi nút bạn tính lại các thông số:
- TotalValue = TotalValue (cũ) + số gói đã chọn * giá trị của mỗi gói.
- M = M (cũ) – số gói đã chọn * trọng lượng của mỗi gói.
- UpperBound = TotalValue + M (mới) * Đơn giá của gói hàng sẽ được xem xét tiếp theo.
- Bước 3: Ở các nút con, bạn sẽ ưu tiên phân nhánh cho nút có giới hạn trên lớn hơn. Các nút con của nút này tương ứng với khả năng lựa chọn gói tiếp theo có đơn giá lớn. Đối với mỗi nút, bạn phải tính lại các thông số TotalValue, M, UpperBound theo công thức đã đề cập ở bước 2.
- Bước 4: Lặp lại Bước 3 với lưu ý: đối với các nút có giới hạn trên thấp hơn hoặc bằng giá trị chi phí tối đa tạm thời của một tùy chọn được tìm thấy, bạn không cần phải phân nhánh cho nút đó nữa.
- Bước 5: Nếu tất cả các nút bị phân nhánh hoặc bị cắt đứt, tùy chọn đắt nhất là tùy chọn cần tìm.
Mã giả cho thuật toán:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
Độ phức tạp của thuật toán:
- Nếu sử dụng thuật toán sắp xếp đơn giản (lựa chọn, bong bóng…) thì độ phức tạp của toàn bộ bài toán là O(n2).
- Nếu sử dụng sắp xếp nhanh hoặc sắp xếp trộn thì độ phức tạp của toàn bộ bài toán là O(nlogn).
Java mã cho Tham lam ba
- Đầu tiên, bạn định nghĩa lớp KnapsackPackage. Lớp này có các thuộc tính là: trọng lượng, giá trị và giá thành tương ứng của từng gói hàng. Giá trị thuộc tính của lớp này được sử dụng để sắp xếp tác vụ trong thuật toán chính. Giá trị của mỗi chi phí là
tỷ lệ của từng gói.
public class KnapsackPackage {
private double weight;
private double value;
private Double cost;
public KnapsackPackage(double weight, double value) {
super();
this.weight = weight;
this.value = value;
this.cost = new Double(value / weight);
}
public double getWeight() {
return weight;
}
public double getValue() {
return value;
}
public Double getCost() {
return cost;
}
}
- Sau đó, bạn tạo một hàm để thực hiện thuật toán Greedy Three.
public void knapsackGreProc(int W[], int V[], int M, int n) {
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int i = 0; i < n; i ++) {
packs[i] = new KnapsackPackage(W[i], V[i]);
}
Arrays.sort(packs, new Comparator<KnapsackPackage>() {
@Override
public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) {
return kPackB.getCost().compareTo(kPackA.getCost());
}
});
int remain = M;
double result = 0d;
int i = 0;
boolean stopProc = false;
while (!stopProc) {
if (packs[i].getWeight() <= remain) {
remain -= packs[i].getWeight();
result += packs[i].getValue();
System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue());
}
if (packs[i].getWeight() > remain) {
i ++;
}
if (i == n) {
stopProc = true;
}
}
System.out.println("Max Value:\t" + result);
}
Giải thích mã:
- Khởi tạo trọng lượng và giá trị cho mỗi gói ba lô.
- Sắp xếp các gói ba lô theo giá thành theo thứ tự giảm dần.
- Nếu chọn gói i.
- Nếu chọn số lượng gói i là đủ.
- Dừng khi duyệt tất cả các gói.
Trong hướng dẫn này, bạn có hai ví dụ. Đây là mã java để chạy chương trình trên với hai ví dụ:
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{15, 10, 2, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{30, 25, 2, 6};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 37;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Bạn có đầu ra:
- Ví dụ đầu tiên:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- Ví dụ thứ hai:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
Phân tích ví dụ đầu tiên:
- Các tham số của bài toán là: n = 4; M = 37.
- Các gói: {i = 1; W[i] = 15; V[i] = 30; Chi phí = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Chi phí = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Chi phí = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Chi phí = 1.5}.
- Bạn sắp xếp các gói theo thứ tự không tăng giá trị đơn giá. Bạn có: {i = 2} -> {tôi = 1} -> {tôi = 4} -> {i = 3}.
Các bước áp dụng thuật toán cho ví dụ đầu tiên:
- Xác định x1, x2, x3, x4 là số lượng từng gói được chọn, tương ứng với gói {i = 2} -> {tôi = 1} -> {tôi = 4} -> {i = 3}.
- Nút gốc N biểu thị trạng thái bạn chưa chọn bất kỳ gói nào. Sau đó:
- Tổng giá trị = 0.
- M = 37 (như đề xuất).
- UpperBound = 37 * 2.5 = 92.5, trong đó 37 là M và 2.5 là đơn giá gói {i = 2}.
- Với gói {i = 2}, bạn có 4 khả năng: chọn 3 gói {i = 2} (x1 = 3); chọn 2 gói {i = 2} (x1 = 2); chọn 1 gói {i = 2} (x1 = 1) và không chọn gói {i = 2} (x1 = 0). Theo 4 khả năng này, bạn phân nhánh nút gốc N thành 4 nút con N[1], N[2], N[3] và N[4].
- Đối với nút con N1, bạn có:
- TotalValue = 0 + 3 * 25 = 75, trong đó 3 là số gói {i = 2} được chọn và 25 là giá trị của mỗi gói {i = 2}.
- M = 37 – 3 * 10 = 7, trong đó 37 là số lượng ban đầu của ba lô, 3 là số kiện hàng {i = 2}, 10 là trọng lượng của mỗi kiện hàng {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, trong đó 75 là TotalValue, 7 là trọng lượng còn lại của ba lô và 2 là đơn giá của gói hàng {i = 1}.
- Tương tự, bạn có thể tính tham số cho các nút N[2], N[3] và N[4], trong đó UpperBound lần lượt là 84, 79 và 74.
- Trong số các nút N[1], N[2], N[3] và N[4], nút N[1] có UpperBound lớn nhất, do đó bạn sẽ phân nhánh nút N[1] trước với hy vọng rằng sẽ có một kế hoạch tốt từ hướng này.
- Từ nút N[1], bạn chỉ có một nút con N[1-1] tương ứng với x2 = 0 (do trọng lượng còn lại của ba lô là 7, trong khi trọng lượng của mỗi gói hàng {i = 1} là 15) . Sau khi xác định được thông số cho nút N[1-1] bạn có UpperBound của N[1-1] là 85.5.
- Bạn tiếp tục phân nhánh nút N[1-1]. Nút N[1-1] có 2 nút con N[1-1-1] và N[1-1-2] tương ứng với x3 = 1 và x3 = 0. Sau khi xác định tham số cho 1 nút này, bạn thấy rằng Biên trên của N[1-1-84] là 1 và của N[1-2-82] là 1 nên bạn tiếp tục phân nhánh nút N[1-1-XNUMX].
- Nút N[1-1-1] có hai nút con là N[1-1-1-1] và N[1-1-1-2], tương ứng với x4 = 1 và x4 = 0. Đây là hai nút lá (đại diện cho tùy chọn) vì đối với mỗi nút, số lượng gói đã được chọn. Trong đó nút N[1-1-1-1] đại diện cho tùy chọn x1 = 3, x2 = 0, x3 = 1 và x4 = 1 cho 83, trong khi nút N[1-1-1-2] đại diện cho tùy chọn x1 = 3, x2 = 0, x3 = 1 và x4 = 01 tại 81. Vậy giá trị tối đa tạm thời ở đây là 83.
- Quay lại nút N[1-1-2], bạn thấy cận trên của N[1-1-2] là 82 < 83 nên bạn cắt bớt nút N[1-1-2].
- Quay lại nút N2, bạn thấy UpperBound của N2 là 84 > 83 nên bạn tiếp tục phân nhánh nút N2. Nút N2 có hai con N[2-1] và N[2-2] tương ứng với x2 = 1 và x2 = 0. Sau khi tính toán tham số cho N[2-1] và N[2-2], bạn thấy Giới hạn trên của N[2-1] là 83 và của N[2-2] là 75.25. Cả hai giá trị này đều không lớn hơn 83 nên cả hai nút đều bị cắt bớt.
- Cuối cùng, nút N3 và N4 cũng được cắt bớt.
- Vì vậy, tất cả các nút trên cây đều được phân nhánh hoặc cắt bớt nên giải pháp tạm thời tốt nhất là tìm kiếm giải pháp tạm thời. Theo đó, bạn cần chọn 3 gói {i = 2}, 1 gói {i = 4} và 3 gói {i = 83} có tổng giá trị là 36, tổng trọng lượng là XNUMX.
Với cách phân tích tương tự ở ví dụ thứ 4, bạn có kết quả: chọn gói 3 (5 lần) và gói 3 (XNUMX lần).
Python3 mã cho Tham lam Ba
- Đầu tiên, bạn định nghĩa lớp KnapsackPackage.
class KnapsackPackage(object):
""" Knapsack Package Data Class """
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.cost = value / weight
def __lt__(self, other):
return self.cost < other.cost
- Sau đó, bạn tạo một hàm để thực hiện thuật toán Greedy Three.
class FractionalKnapsack(object):
def __init__(self):
def knapsackGreProc(self, W, V, M, n):
packs = []
for i in range(n):
packs.append(KnapsackPackage(W[i], V[i]))
packs.sort(reverse = True)
remain = M
result = 0
i = 0
stopProc = False
while (stopProc != True):
if (packs[i].weight <= remain):
remain -= packs[i].weight;
result += packs[i].value;
print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
if (packs[i].weight > remain):
i += 1
if (i == n):
stopProc = True
print("Max Value:\t", result)
Giải thích mã:
- Khởi tạo trọng lượng và giá trị cho mỗi gói ba lô.
- Sắp xếp các gói ba lô theo giá thành theo thứ tự giảm dần.
- Nếu chọn gói i.
- Nếu chọn số lượng gói i là đủ.
- Dừng khi duyệt tất cả các gói.
Đây là Python3 code để chạy chương trình trên với ví dụ đầu tiên:
if __name__ == "__main__":
W = [15, 10, 2, 4]
V = [30, 25, 2, 6]
M = 37
n = 4
proc = FractionalKnapsack()
proc.knapsackGreProc(W, V, M, n)
Bạn có đầu ra:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Mã C# cho Tham lam ba
- Đầu tiên, bạn định nghĩa lớp KnapsackPackage.
using System;
namespace KnapsackProblem
{
public class KnapsackPackage
{
private double weight;
private double value;
private double cost;
public KnapsackPackage(double weight, double value)
{
this.weight = weight;
this.value = value;
this.cost = (double) value / weight;
}
public double Weight
{
get { return weight; }
}
public double Value
{
get { return value; }
}
public double Cost
{
get { return cost; }
}
}
}
- Sau đó, bạn tạo một hàm để thực hiện thuật toán Greedy Three.
using System;
namespace KnapsackProblem
{
public class FractionalKnapsack
{
public FractionalKnapsack()
{
}
public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int k = 0; k < n; k++)
packs[k] = new KnapsackPackage(W[k], V[k]);
Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>(
(kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));
double remain = M;
double result = 0d;
int i = 0;
bool stopProc = false;
while (!stopProc)
{
if (packs[i].Weight <= remain)
{
remain -= packs[i].Weight;
result += packs[i].Value;
Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value);
}
if (packs[i].Weight > remain)
{
i++;
}
if (i == n)
{
stopProc = true;
}
}
Console.WriteLine("Max Value:\t" + result);
}
}
}
Giải thích mã:
- Khởi tạo trọng lượng và giá trị cho mỗi gói ba lô.
- Sắp xếp các gói ba lô theo giá thành theo thứ tự giảm dần.
- Nếu chọn gói i.
- Nếu chọn số lượng gói i là đủ.
- Dừng khi duyệt tất cả các gói.
Đây là mã C# để chạy chương trình trên với ví dụ đầu tiên:
public void run()
{
/*
* Pack and Weight - Value
*/
int[] W = new int[]{15, 10, 2, 4};
//int[] W = new int[] { 12, 2, 1, 1, 4 };
int[] V = new int[]{30, 25, 2, 6};
//int[] V = new int[] { 4, 2, 1, 2, 10 };
/*
* Max Weight
*/
int M = 37;
//int M = 15;
int n = V.Length;
/*
* Run the algorithm
*/
KnapsackGreProc(W, V, M, n);
}
Bạn có đầu ra:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Phản ví dụ của Greedy Three
Thuật toán của Greedy Three giải quyết nhanh chóng và cũng có thể tối ưu trong một số trường hợp. Tuy nhiên, trong một số trường hợp đặc biệt nó không cho lời giải tối ưu. Ở đây bạn có một phản ví dụ:
- Các tham số của bài toán là: n = 3; M = 10.
- Các gói: {i = 1; W[i] = 7; V[i] = 9; Chi phí = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Chi phí = 1}; {i = 3; W[i] = 4; V[i] = 4; Chi phí = 1}.
- Thuật toán sẽ chọn (gói 1) có tổng giá trị là 9, còn phương án tối ưu của bài toán là (gói 2, gói 3) có tổng giá trị là 10.
Đây là mã java để chạy chương trình trên với ví dụ ngược lại:
public void run() {
/*
* Pack and Weight - Value
*/
int W[] = new int[]{7, 6, 4};
int V[] = new int[]{9, 6, 4};
/*
* Max Weight
*/
int M = 10;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Đây là kết quả:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Đó là tất cả vấn đề về chiếc ba lô phân số.
