Problem frakcijskog naprtnjače: pohlepni algoritam s primjerom

Što je pohlepna strategija?

Pohlepni algoritmi su poput algoritama dinamičkog programiranja koji se često koriste za rješavanje optimalnih problema (pronalaženje najboljih rješenja problema prema određenom kriteriju).

Pohlepni algoritmi implementiraju optimalne lokalne odabire u nadi da će ti odabiri dovesti do optimalnog globalnog rješenja za problem koji treba riješiti. Pohlepne algoritme često nije previše teško postaviti, brzi su (vremenska složenost često je linearna funkcija ili zapravo funkcija drugog reda). Osim toga, te programe nije teško ispraviti i koriste manje memorije. Ali rezultati nisu uvijek optimalno rješenje.

Pohlepne strategije se često koriste za rješavanje problema kombinatorne optimizacije izgradnjom opcije A. Opcija A se konstruira odabirom svake komponente Ai od A dok se ne završi (dovoljno n komponenti). Za svaki Ai odabirete Ai optimalno. Na taj je način moguće da u zadnjem koraku nemate što odabrati osim prihvatiti posljednju preostalu vrijednost.

Dvije su ključne komponente pohlepnih odluka:

Put pohlepne selekcije. Možete odabrati koje je rješenje trenutno najbolje i zatim riješiti podproblem koji proizlazi iz posljednjeg odabira. Odabir pohlepnih algoritama može ovisiti o prethodnim odabirima. Ali to ne može ovisiti o nekom budućem odabiru ili o rješenjima podproblema. Algoritam se razvija na način da odabire u petlji, u isto vrijeme smanjujući zadani problem na manje podprobleme.
Optimalna podkonstrukcija. Izvodite optimalnu podstrukturu za problem ako optimalno rješenje ovog problema sadrži optimalna rješenja njegovih podproblema.

Pohlepni algoritam ima pet komponenti:

Skup kandidata iz kojih se stvaraju rješenja.
Funkcija odabira za odabir najboljeg kandidata za dodavanje rješenju.
Izvediva funkcija koristi se za odlučivanje može li se kandidat koristiti za izradu rješenja.
Ciljna funkcija, fiksiranje vrijednosti rješenja ili nepotpunog rješenja.
Funkcija evaluacije, koja pokazuje kada pronađete potpuno rješenje.

Ideja Greedy One

Uz prvu ideju, imate sljedeće korake Greedy One:

Poredaj u nerastućem redoslijedu vrijednosti.
Zauzvrat razmotrite naručene pakete, stavite predmetni paket u naprtnjaču ako je preostali kapacitet naprtnjače dovoljan da ga primi (što znači da ukupna težina paketa koji su stavljeni u naprtnjaču i težina razmatranih paketa ne prelazi kapacitet naprtnjače).

Međutim, ovaj pohlepni algoritam ne daje uvijek optimalno rješenje. Evo ti kontraprimjera:

Parametri problema su: n = 3; M = 19.
Paketi: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Velika vrijednost, ali i velika težina.
Algoritam će odabrati paket 1 ukupne vrijednosti 20, dok će optimalno rješenje problema biti odabrano (paket 2, paket 3) ukupne vrijednosti 24.

Ideja Greedy Two

S drugom idejom, imate sljedeće korake Greedy Two:

Poredaj neopadajućim redoslijedom težine.
Zauzvrat razmotrite naručene pakete, stavite predmetni paket u naprtnjaču ako je preostali kapacitet naprtnjače dovoljan da ga primi (što znači da ukupna težina paketa koji su stavljeni u naprtnjaču i težina razmatranih paketa ne prelazi kapacitet naprtnjače).

Međutim, ovaj pohlepni algoritam ne daje uvijek optimalno rješenje. Evo ti kontraprimjera:

Parametri problema su: n = 3; M = 11.
Paketi: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Mala težina, ali vrijednost je također vrlo mala.
Algoritam će odabrati (paket 1, paket 2) ukupne vrijednosti 26, dok je optimalno rješenje zadatka (paket 3) ukupne vrijednosti 28.

Ideja Greedy Three

S trećom idejom imate sljedeće korake Greedy Three. Zapravo, ovo je najrašireniji algoritam.

Sortirajte pakete prema redoslijedu nenarastanja vrijednosti jedinične cijene . Imaš:

Zauzvrat razmotrite naručene pakete, stavite predmetni paket u naprtnjaču ako je preostali kapacitet naprtnjače dovoljan da ga primi (što znači da ukupna težina paketa koji su stavljeni u naprtnjaču i težina razmatranih paketa ne prelazi kapacitet naprtnjače).

Ideja: Pohlepna ideja tog problema je izračunati omjer svakog . Zatim poredajte ove omjere silaznim redoslijedom. Vi ćete izabrati najviše paket i kapacitet naprtnjače može sadržavati taj paket (ostatak > w_i). Svaki put kada se paket stavi u naprtnjaču, to će također smanjiti kapacitet naprtnjače.

Način odabira paketa:

Razmotrite niz jediničnih troškova. Pakete birate prema padajućim jediničnim troškovima.

Pretpostavimo da ste pronašli djelomično rješenje: (x₁,…, X_i).
Dobiva se vrijednost naprtnjače:

Odgovara težini paketa koji su stavljeni u naprtnjaču:

Prema tome, preostala granica težine naprtnjače je:

Koraci algoritma

Vidite da je ovo problem pronalaženja max. Popis paketa poredan je silaznim redoslijedom jediničnih troškova kako bi se razmotrilo grananje.

Korak 1: Korijen čvora predstavlja početno stanje naprtnjače, gdje niste odabrali nijedan paket.
Ukupna vrijednost = 0.
Gornja granica korijenskog čvora Gornja granica = M * Maksimalni jedinični trošak.
Korak 2: Korijen čvora će imati podređene čvorove koji odgovaraju mogućnosti odabira paketa s najvećim jediničnim troškom. Za svaki čvor ponovno izračunavate parametre:
TotalValue = TotalValue (staro) + broj odabranih paketa * vrijednost svakog paketa.
M = M (staro) – broj odabranih paketa * težina svakog paketa.
Gornja granica = TotalValue + M (novo) * Jedinični trošak pakiranja koji će se uzeti u obzir sljedeći.
Korak 3: U podređenim čvorovima dat ćete prednost grananju za čvor koji ima veću gornju granicu. Djeca ovog čvora odgovaraju mogućnosti odabira sljedećeg paketa koji ima veliku jediničnu cijenu. Za svaki čvor morate ponovno izračunati parametre TotalValue, M, UpperBound prema formuli spomenutoj u koraku 2.
Korak 4: Ponovite korak 3 uz napomenu: za čvorove čija je gornja granica niža ili jednaka vrijednosti privremenog maksimalnog troška pronađene opcije, više ne morate granati za taj čvor.
Korak 5: Ako su svi čvorovi razgranati ili odsječeni, najskuplja je opcija koju treba tražiti.

Pseudo kod za algoritam:

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

Složenost algoritma:

Ako se koristi jednostavan algoritam sortiranja (odabir, mjehurić...) tada je složenost cijelog problema O(n2).
Ako koristite brzo sortiranje ili sortiranje spajanjem tada je složenost cijelog problema O(nlogn).

Java šifra za Greedy Three

Prvo, definirate klasu KnapsackPackage. Ova klasa ima svojstva: težinu, vrijednost i odgovarajuću cijenu svakog paketa. Trošak svojstva ove klase koristi se za zadatak sortiranja u glavnom algoritmu. Vrijednost svakog troška je omjer svakog paketa.

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;
	}

}

Zatim kreirate funkciju za izvođenje 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);
}

Objašnjenje koda:

Inicijalizirajte težinu i vrijednost za svaki paket naprtnjače.
Poredaj pakete s naprtnjačama prema cijeni silaznim redoslijedom.
Ako odaberete paket i.
Ako odaberete broj paketa i dovoljan je.
Zaustavite se prilikom pregledavanja svih paketa.

U ovom vodiču imate dva primjera. Evo java koda za pokretanje gornjeg programa s dva primjera:

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);
}

Imate izlaz:

Prvi primjer:

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

Drugi primjer:

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

Analiziraj prvi primjer:

Parametri problema su: n = 4; M = 37.
Paketi: {i = 1; W[i] = 15; V[i] = 30; Trošak = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Trošak = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Trošak = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Trošak = 1.5}.
Pakete sortirate prema redoslijedu bez povećanja vrijednosti jediničnih troškova. Imate: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.

Koraci za primjenu algoritma za prvi primjer:

Definirajte x1, x2, x3, x4 je broj svakog odabranog paketa, koji odgovara paketu {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Node root N predstavlja stanje da niste odabrali nijedan paket. Zatim:
- Ukupna vrijednost = 0.
- M = 37 (kako je predloženo).
- Gornja granica = 37 * 2.5 = 92.5, od čega je 37 M, a 2.5 jedinična cijena paketa {i = 2}.
S paketom {i = 2} imate 4 mogućnosti: odaberite 3 paketa {i = 2} (x1 = 3); odaberite 2 paketa {i = 2} (x1 = 2); odaberite 1 paket {i = 2} (x1 = 1), a ne odaberite paket {i = 2} (x1 = 0). U skladu s ove 4 mogućnosti, granate korijenski čvor N na 4 djeteta N[1], N[2], N[3] i N[4].
Za podređeni čvor N1 imate:
- TotalValue = 0 + 3 * 25 = 75, gdje je 3 broj odabranog paketa {i = 2}, a 25 je vrijednost svakog paketa {i = 2}.
- M = 37 – 3 * 10 = 7, gdje je 37 početna količina naprtnjače, 3 je broj paketa {i = 2}, 10 je težina svakog paketa {i = 2}.
- Gornja granica = 75 + 7 * 2 = 89, gdje je 75 TotalValue, 7 je preostala težina naprtnjače, a 2 je jedinična cijena paketa {i = 1}.
Slično, možete izračunati parametre za čvorove N[2], N[3] i N[4], u kojima je gornja granica 84, 79 odnosno 74.
Među čvorovima N[1], N[2], N[3] i N[4], čvor N[1] ima najveću gornju granicu, tako da ćete prvo granati čvor N[1] u nadi da će postojati dobar plan iz ovog smjera.
Iz čvora N[1], imate samo jedan podređeni čvor N[1-1] koji odgovara x2 = 0 (zbog preostale težine ruksaka je 7, dok je težina svakog paketa {i = 1} 15) . Nakon određivanja parametara za gumb N[1-1] imate gornju granicu N[1-1] 85.5.
Nastavljate s grananjem čvora N[1-1]. Čvor N[1-1] ima 2 djece N[1-1-1] i N[1-1-2] što odgovara x3 = 1 i x3 = 0. Nakon određivanja parametara za ova dva čvora, vidite da je Gornja granica N[1-1-1] je 84, a N[1-1-2] je 82, tako da nastavljate s grananjem čvora N[1-1-1].
Čvor N[1-1-1] ima dva djeteta, N[1-1-1-1] i N[1-1-1-2], što odgovara x4 = 1 i x4 = 0. Ovo su dva lisna čvora (predstavlja opciju) jer je za svaki čvor odabran broj paketa. U kojem čvor N[1-1-1-1] predstavlja opciju x1 = 3, x2 = 0, x3 = 1 i x4 = 1 za 83, dok čvor N[1-1-1-2] predstavlja opciju x1 = 3, x2 = 0, x3 = 1 i x4 = 01 na 81. Dakle, privremena najveća vrijednost ovdje je 83.
Vraćajući se natrag na čvor N[1-1-2], vidite da je gornja granica N[1-1-2] 82 < 83, tako da skratite čvor N[1-1-2].
Vraćajući se natrag na čvor N2, vidite da je gornja granica N2 84 > 83, tako da nastavljate s grananjem čvora N2. Čvor N2 ima dva djeteta N[2-1] i N[2-2] što odgovara x2 = 1 i x2 = 0. Nakon izračuna parametara za N[2-1] i N[2-2], vidite gornja granica za N[2-1] je 83, a za N[2-2] je 75.25. Nijedna od ovih vrijednosti nije veća od 83 pa su oba čvora odrezana.
Konačno, čvorovi N3 i N4 također su odrezani.
Dakle, svi su čvorovi na stablu razgranati ili podrezani, tako da je najbolje privremeno rješenje ono koje treba tražiti. U skladu s tim, trebate odabrati 3 paketa {i = 2}, 1 paket {i = 4} i jedan paket {i = 3} ukupne vrijednosti 83, ukupna težina je 36.

S istom analizom drugog primjera, imate rezultat: odaberite paket 4 (3 puta) i paket 5 (3 puta).

Python3 kod za Greedy Three

Prvo, definirate klasu 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

Zatim kreirate funkciju za izvođenje 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)

Objašnjenje koda:

Inicijalizirajte težinu i vrijednost za svaki paket naprtnjače.
Poredaj pakete s naprtnjačama prema cijeni silaznim redoslijedom.
Ako odaberete paket i.
Ako odaberete broj paketa i dovoljan je.
Zaustavite se prilikom pregledavanja svih paketa.

Ovdje je Python3 kod za pokretanje gornjeg programa s prvim primjerom:

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)

Imate izlaz:

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

C# kod za Greedy Three

Prvo, definirate klasu 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; }
        }
    }
}

Zatim kreirate funkciju za izvođenje 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);
        }        
    }
}

Objašnjenje koda:

Inicijalizirajte težinu i vrijednost za svaki paket naprtnjače.
Poredaj pakete s naprtnjačama prema cijeni silaznim redoslijedom.
Ako odaberete paket i.
Ako odaberete broj paketa i dovoljan je.
Zaustavite se prilikom pregledavanja svih paketa.

Evo C# koda za pokretanje gornjeg programa s prvim primjerom:

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);
}

Imate izlaz:

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

Protuprimjer Greedy Three

Algoritam Greedy Three brzo se rješava i može biti optimalan u nekim slučajevima. Međutim, u nekim posebnim slučajevima ne daje optimalno rješenje. Evo ti kontraprimjera:

Parametri problema su: n = 3; M = 10.
Paketi: {i = 1; W[i] = 7; V[i] = 9; Trošak = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Trošak = 1}; {i = 3; W[i] = 4; V[i] = 4; Trošak = 1}.
Algoritam će odabrati (paket 1) ukupne vrijednosti 9, dok je optimalno rješenje zadatka (paket 2, paket 3) ukupne vrijednosti 10.

Evo java koda za pokretanje gornjeg programa s protuprimjerom:

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);
}

Evo rezultata:

Pack 0 - Weight 7.0 - Value 9.0
Max Value:	9.0

To je sve što se tiče problema Fractional Naprtnjače.

Možda ti se svidi:

Što je pohlepna strategija?

Ideja Greedy One

Ideja Greedy Two

POVEZANI ČLANCI

Ideja Greedy Three

Koraci algoritma

Java šifra za Greedy Three

Python3 kod za Greedy Three

C# kod za Greedy Three

Protuprimjer Greedy Three

POVEZANI ČLANCI