Masalah Ransel Pecahan: Algoritma Greedy dengan Contoh
Sarah Chen
Apa itu Strategi Serakah?
Algoritma Greedy seperti algoritma pemrograman dinamis yang sering digunakan untuk memecahkan masalah optimal (menemukan solusi terbaik dari masalah tersebut menurut kriteria tertentu).
Algoritma greedy menerapkan pilihan lokal yang optimal dengan harapan bahwa pilihan tersebut akan menghasilkan solusi global yang optimal untuk masalah yang ingin dipecahkan. Algoritma greedy sering kali tidak terlalu sulit untuk disiapkan, cepat (kompleksitas waktu sering kali merupakan fungsi linear atau fungsi orde kedua). Selain itu, program ini tidak sulit untuk di-debug dan menggunakan lebih sedikit memori. Namun, hasilnya tidak selalu merupakan solusi yang optimal.
Strategi serakah sering digunakan untuk menyelesaikan masalah optimasi kombinatorial dengan membangun opsi A. Opsi A dibangun dengan memilih setiap komponen Ai dari A hingga selesai (cukup n komponen). Untuk setiap Ai, Anda memilih Ai secara optimal. Dengan cara ini, mungkin saja pada langkah terakhir Anda tidak punya pilihan selain menerima nilai terakhir yang tersisa.
Ada dua komponen penting dari keputusan serakah:
- Cara pemilihan greedy. Anda dapat memilih solusi mana yang terbaik saat ini dan kemudian memecahkan submasalah yang timbul dari pemilihan terakhir. Pemilihan algoritma greedy dapat bergantung pada pemilihan sebelumnya. Namun, pemilihan tersebut tidak dapat bergantung pada pemilihan di masa mendatang atau bergantung pada solusi submasalah. Algoritma tersebut berkembang dengan cara membuat pemilihan secara berulang, sekaligus mengecilkan masalah yang diberikan menjadi submasalah yang lebih kecil.
- Substruktur optimal. Anda melakukan substruktur optimal untuk suatu masalah jika solusi optimal dari masalah ini berisi solusi optimal untuk submasalahnya.
Algoritma serakah memiliki lima komponen:
- Sekumpulan kandidat yang akan dijadikan solusi.
- Fungsi seleksi, untuk memilih kandidat terbaik untuk ditambahkan ke solusi.
- Fungsi layak digunakan untuk memutuskan apakah seorang kandidat dapat digunakan untuk membangun solusi.
- Fungsi tujuan, yang menetapkan nilai solusi atau solusi tidak lengkap.
- Fungsi evaluasi, menunjukkan kapan Anda menemukan solusi lengkap.
Ide tentang Orang yang Serakah
Dengan ide pertama, Anda memiliki langkah-langkah berikut dari Greedy One:
- Urutkan dalam urutan nilai yang tidak bertambah.
- Pertimbangkan paket yang dipesan secara bergantian, masukkan paket pertimbangan ke dalam ransel jika sisa kapasitas ransel cukup untuk menampungnya (artinya berat total paket yang dimasukkan ke dalam ransel dan berat paket pertimbangan tidak melebihi kapasitas ransel).
Namun algoritma serakah ini tidak selalu memberikan solusi optimal. Di sini Anda memiliki contoh tandingan:
- Parameter masalahnya adalah: n = 3; L = 19.
- Paket-paketnya: {i = 1; W[saya] = 14; V[saya] = 20}; {saya = 2; W[saya] = 6; V[saya] = 16}; {saya = 3; W[saya] = 10; V[saya] = 8} -> Nilai bagus tetapi juga bobotnya besar.
- Algoritma akan memilih paket 1 dengan nilai total 20, sedangkan solusi optimal dari masalah tersebut dipilih (paket 2, paket 3) dengan nilai total 24.
Ide tentang Serakah Dua
Dengan ide kedua, Anda memiliki langkah-langkah Greedy Two berikut:
- Urutkan dalam urutan bobot yang tidak menurun.
- Pertimbangkan paket yang dipesan secara bergantian, masukkan paket pertimbangan ke dalam ransel jika sisa kapasitas ransel cukup untuk menampungnya (artinya berat total paket yang dimasukkan ke dalam ransel dan berat paket pertimbangan tidak melebihi kapasitas ransel).
Namun algoritma serakah ini tidak selalu memberikan solusi optimal. Di sini Anda memiliki contoh tandingan:
- Parameter masalahnya adalah: n = 3; L = 11.
- Paket-paketnya: {i = 1; W[saya] = 5; V[saya] = 10}; {saya = 2; W[saya] = 6; V[saya] = 16}; {saya = 3; W[saya] = 10; V[saya] = 28} -> Ringan namun nilainya juga sangat ringan.
- Algoritma akan memilih (paket 1, paket 2) dengan nilai total 26, sedangkan solusi optimal dari permasalahan tersebut adalah (paket 3) dengan nilai total 28.
Ide Tiga Serakah
Dengan ide ketiga, Anda memiliki langkah-langkah berikut dari Greedy Three. Faktanya, ini adalah algoritma yang paling banyak digunakan.
- Urutkan paket berdasarkan urutan nilai biaya satuan yang tidak bertambah
. Kamu punya:
- Pertimbangkan paket yang dipesan secara bergantian, masukkan paket pertimbangan ke dalam ransel jika sisa kapasitas ransel cukup untuk menampungnya (artinya berat total paket yang dimasukkan ke dalam ransel dan berat paket pertimbangan tidak melebihi kapasitas ransel).
Ide: Ide serakah dari soal itu adalah menghitung 
rasio masing-masing 
. Kemudian urutkan rasio ini dengan urutan menurun. Anda akan memilih yang tertinggi paket dan kapasitas ransel dapat memuat paket tersebut (tetap > wi). Setiap paket dimasukkan ke dalam knapsack maka kapasitas knapsack juga akan berkurang.
Cara memilih paket:
- Pertimbangkan rangkaian biaya unit. Anda memilih paket berdasarkan penurunan biaya unit.
- Misalkan Anda menemukan solusi parsial: (x1,…, Xi).
- Nilai ransel yang didapat :
- Sesuai dengan berat paket yang dimasukkan ke dalam ransel:
- Jadi, batas berat sisa ransel tersebut adalah:
Langkah-langkah Algoritma
Anda lihat ini adalah masalah menemukan maks. Daftar paket diurutkan berdasarkan biaya unit untuk mempertimbangkan percabangan.
- Langkah 1: Root node mewakili keadaan awal ransel, di mana Anda belum memilih paket apa pun.
- Nilai Total = 0.
- Batas atas dari simpul akar UpperBound = M * Biaya unit maksimum.
- Langkah 2: Node root akan memiliki node anak yang sesuai dengan kemampuan untuk memilih paket dengan biaya unit terbesar. Untuk setiap node, Anda menghitung ulang parameternya:
- TotalValue = TotalValue (lama) + jumlah paket yang dipilih * nilai setiap paket.
- M = M (lama) – jumlah paket yang dipilih * berat setiap paket.
- UpperBound = TotalValue + M (baru) * Biaya unit paket yang akan dipertimbangkan selanjutnya.
- Langkah 3: Pada node anak, Anda akan memprioritaskan percabangan untuk node yang memiliki batas atas lebih besar. Anak-anak dari node ini berhubungan dengan kemampuan memilih paket berikutnya yang memiliki biaya unit besar. Untuk setiap node, Anda harus menghitung ulang parameter TotalValue, M, UpperBound sesuai rumus yang disebutkan pada langkah 2.
- Langkah 4: Ulangi Langkah 3 dengan catatan: untuk node dengan batas atas lebih rendah atau sama nilainya dengan biaya maksimum sementara dari opsi yang ditemukan, Anda tidak perlu melakukan pencabangan lagi untuk node tersebut.
- Langkah 5: Jika semua node bercabang atau terpotong, opsi yang paling mahal adalah yang harus dicari.
Kode semu untuk algoritma:
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
Kompleksitas algoritma:
- Jika menggunakan algoritma sorting sederhana (selection, bubble…) maka kompleksitas keseluruhan permasalahannya adalah O(n2).
- Jika menggunakan quick sort atau merge sort maka kompleksitas seluruh masalahnya adalah O(nlogn).
Java kode untuk Greedy Three
- Pertama, Anda mendefinisikan kelas KnapsackPackage. Kelas ini memiliki properti yaitu: bobot, nilai dan biaya yang sesuai dari setiap paket. Biaya properti kelas ini digunakan untuk tugas pengurutan di algoritma utama. Nilai setiap biaya adalah
rasio setiap paket.
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;
}
}
- Anda kemudian membuat fungsi untuk menjalankan algoritma 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);
}
Penjelasan kode:
- Inisialisasi bobot dan nilai untuk setiap paket knapsack.
- Urutkan paket knapsack berdasarkan biaya dengan urutan menurun.
- Jika pilih paket i.
- Jika memilih jumlah paket i sudah cukup.
- Berhenti saat menelusuri semua paket.
Dalam tutorial ini, Anda memiliki dua contoh. Berikut adalah kode java untuk menjalankan program di atas dengan dua contoh:
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);
}
Anda memiliki hasilnya:
- Contoh Pertama:
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
- Contoh Kedua:
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
Analisis contoh pertama:
- Parameter masalahnya adalah: n = 4; L = 37.
- Paket-paketnya: {i = 1; W[saya] = 15; V[saya] = 30; Biaya = 2.0}; {saya = 2; W[saya] = 10; V[saya] = 25; Biaya = 2.5}; {saya = 3; W[saya] = 2; V[saya] = 4; Biaya = 1.0}; {saya = 4; W[saya] = 4; V[saya] = 6; Biaya = 1.5}.
- Anda mengurutkan paket dalam urutan tidak ada peningkatan nilai biaya per unit. Anda mempunyai: {i = 2} -> {saya = 1} -> {saya = 4} -> {saya = 3}.
Langkah-langkah penerapan algoritma untuk contoh pertama:
- Tentukan x1, x2, x3, x4 adalah jumlah setiap paket yang dipilih, sesuai dengan paket {i = 2} -> {saya = 1} -> {saya = 4} -> {saya = 3}.
- Node root N mewakili keadaan bahwa Anda belum memilih paket apa pun. Kemudian:
- Nilai Total = 0.
- M = 37 (seperti yang diusulkan).
- Batas Atas = 37 * 2.5 = 92.5, dimana 37 adalah M dan 2.5 adalah biaya satuan paket {i = 2}.
- Dengan paket {i = 2}, Anda memiliki 4 kemungkinan: pilih 3 paket {i = 2} (x1 = 3); pilih 2 paket {i = 2} (x1 = 2); pilih 1 paket {i = 2} (x1 = 1) dan bukan pilih paket {i = 2} (x1 = 0). Sesuai dengan 4 kemungkinan ini, Anda mencabangkan simpul akar N menjadi 4 anak N[1], N[2], N[3] dan N[4].
- Untuk simpul anak N1, Anda memiliki:
- TotalValue = 0 + 3 * 25 = 75, dimana 3 adalah jumlah paket {i = 2} yang dipilih dan 25 adalah nilai setiap paket {i = 2}.
- M = 37 – 3 * 10 = 7, dimana 37 adalah jumlah awal ransel, 3 adalah jumlah bungkusan {i = 2}, 10 adalah berat tiap bungkusan {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, dimana 75 adalah TotalValue, 7 adalah sisa berat ransel dan 2 adalah biaya satuan paket {i = 1}.
- Demikian pula, Anda dapat menghitung parameter untuk node N[2], N[3] dan N[4], dengan Batas Atas masing-masing adalah 84, 79 dan 74.
- Di antara node N[1], N[2], N[3] dan N[4], node N[1] memiliki Batas Atas yang paling besar, jadi Anda akan mencabangkan node N[1] terlebih dahulu dengan harapan akan ada a rencana bagus dari arah ini.
- Dari node N[1], Anda hanya memiliki satu node anak N[1-1] yang bersesuaian dengan x2 = 0 (karena sisa berat ransel adalah 7, sedangkan berat setiap paket {i = 1} adalah 15) . Setelah menentukan parameter untuk tombol N[1-1] Anda memiliki Batas Atas N[1-1] adalah 85.5.
- Anda melanjutkan percabangan simpul N[1-1]. Node N[1-1] mempunyai 2 turunan N[1-1-1] dan N[1-1-2] yang sesuai dengan x3 = 1 dan x3 = 0. Setelah menentukan parameter untuk kedua node ini, Anda akan melihat bahwa Batas Atas N[1-1-1] adalah 84 dan Batas Atas N[1-1-2] adalah 82, jadi lanjutkan percabangan simpul N[1-1-1].
- Node N[1-1-1] mempunyai dua anak, N[1-1-1-1] dan N[1-1-1-2], yang berkorespondensi dengan x4 = 1 dan x4 = 0. Ini adalah dua node daun (mewakili opsi) karena untuk setiap node jumlah paket telah dipilih. Dimana node N[1-1-1-1] mewakili opsi x1 = 3, x2 = 0, x3 = 1 dan x4 = 1 untuk 83, sedangkan node N[1-1-1-2] mewakili opsi x1 = 3, x2 = 0, x3 = 1 dan x4 = 01 sebesar 81. Jadi nilai maksimum sementara disini adalah 83.
- Kembali ke simpul N[1-1-2], Anda melihat bahwa Batas Atas N[1-1-2] adalah 82 < 83, jadi Anda memangkas simpul N[1-1-2].
- Kembali ke node N2, Anda melihat Batas Atas N2 adalah 84 > 83, jadi Anda melanjutkan percabangan node N2. Node N2 memiliki dua turunan N[2-1] dan N[2-2] yang bersesuaian dengan x2 = 1 dan x2 = 0. Setelah menghitung parameter untuk N[2-1] dan N[2-2], Anda akan melihat Batas Atas N[2-1] adalah 83 dan Batas Atas N[2-2] adalah 75.25. Tak satu pun dari nilai-nilai ini lebih besar dari 83 sehingga kedua node dipangkas.
- Terakhir, node N3 dan N4 juga dipangkas.
- Jadi semua simpul pada pohon tersebut bercabang atau dipangkas sehingga solusi sementara terbaiklah yang harus dicari. Oleh karena itu, Anda perlu memilih 3 paket {i = 2}, 1 paket {i = 4} dan satu paket {i = 3} dengan nilai total 83, bobot total 36.
Dengan analisa yang sama pada contoh kedua, Anda mendapatkan hasil: pilih paket 4 (3 kali) dan paket 5 (3 kali).
Python3 kode untuk Greedy Three
- Pertama, Anda mendefinisikan kelas 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
- Anda kemudian membuat fungsi untuk menjalankan algoritma 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)
Penjelasan kode:
- Inisialisasi bobot dan nilai untuk setiap paket knapsack.
- Urutkan paket knapsack berdasarkan biaya dengan urutan menurun.
- Jika pilih paket i.
- Jika memilih jumlah paket i sudah cukup.
- Berhenti saat menelusuri semua paket.
Berikut ini adalah Python3 kode untuk menjalankan program di atas dengan contoh pertama:
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)
Anda memiliki hasilnya:
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
Kode C# untuk Greedy Three
- Pertama, Anda mendefinisikan kelas 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; }
}
}
}
- Anda kemudian membuat fungsi untuk menjalankan algoritma 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);
}
}
}
Penjelasan kode:
- Inisialisasi bobot dan nilai untuk setiap paket knapsack.
- Urutkan paket knapsack berdasarkan biaya dengan urutan menurun.
- Jika pilih paket i.
- Jika memilih jumlah paket i sudah cukup.
- Berhenti saat menelusuri semua paket.
Berikut adalah kode C# untuk menjalankan program di atas dengan contoh pertama:
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);
}
Anda memiliki hasilnya:
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
Contoh tandingan dari Greedy Three
Algoritme Greedy Three menyelesaikan dengan cepat dan juga bisa optimal dalam beberapa kasus. Namun pada beberapa kasus tertentu tidak memberikan solusi optimal. Di sini Anda memiliki contoh tandingan:
- Parameter masalahnya adalah: n = 3; L = 10.
- Paket-paketnya: {i = 1; W[saya] = 7; V[saya] = 9; Biaya = 9/7}; {saya = 2; W[saya] = 6; V[saya] = 6; Biaya = 1}; {saya = 3; W[saya] = 4; V[saya] = 4; Biaya = 1}.
- Algoritma akan memilih (paket 1) dengan nilai total 9, sedangkan solusi optimal dari permasalahan tersebut adalah (paket 2, paket 3) dengan nilai total 10.
Berikut adalah kode java untuk menjalankan program di atas dengan contoh tandingan:
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);
}
Inilah hasilnya:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Itu saja untuk masalah Fractional Knapsack.
