0/1 Knapsack Problem Fix med hjälp av dynamiskt programmeringsexempel
Sarah Chen
Vad är knepsäcksproblemet?
Knapsäcksproblem Algoritm är ett mycket användbart problem inom kombinatorik. I snabbköpet finns n paket (n ≤ 100) paketet i har vikt W[i] ≤ 100 och värde V[i] ≤ 100. En tjuv bryter sig in i snabbköpet, tjuven kan inte bära vikt som överstiger M (M ≤ 100) ). Problemet som ska lösas här är: vilka paket kommer tjuven att ta bort för att få det högsta värdet?
Ingång:
- Maxvikt M och antalet förpackningar n.
- Array av vikt W[i] och motsvarande värde V[i].
Produktion:
- Maximera värde och motsvarande vikt i kapacitet.
- Vilka paket tjuven ska ta bort.
Ryggsäcksalgoritm kan ytterligare delas in i två typer:
- 0/1 Knapsack-problemet med dynamisk programmering. I denna Knapsack-algoritmtyp kan varje paket tas eller inte tas. Dessutom kan tjuven inte ta en bråkdel av ett tagit paket eller ta ett paket mer än en gång. Denna typ kan lösas med Dynamic Programming Approach.
- Fractional Knapsack problemalgoritm. Denna typ kan lösas med Greedy Strategy.
Hur man löser Knapsack-problem med hjälp av dynamisk programmering med exempel
I dela-och-härska-strategin delar du upp problemet som ska lösas i delproblem. Delproblemen är vidare uppdelade i mindre delproblem. Den uppgiften kommer att fortsätta tills du får delproblem som enkelt kan lösas. Men i processen med en sådan uppdelning kan du stöta på samma problem många gånger.
Grundidén med Knapsack dynamisk programmering är att använda en tabell för att lagra lösningar på lösta delproblem. Om du möter ett delproblem igen behöver du bara ta lösningen i tabellen utan att behöva lösa det igen. Därför är algoritmerna designade av dynamisk programmering mycket effektiva.
För att lösa ett problem genom dynamisk programmering måste du göra följande uppgifter:
- Hitta lösningar på de minsta delproblemen.
- Ta reda på formeln (eller regeln) för att bygga en lösning av delproblem genom lösningar av även de minsta delproblemen.
- Skapa en tabell som lagrar lösningarna för delproblem. Beräkna sedan lösningen av delproblem enligt den hittade formeln och spara i tabellen.
- Från de lösta delproblemen hittar du lösningen på det ursprungliga problemet.
Analysera 0/1 Knapsack Problem
När du analyserar 0/1 Knapsack-problem med dynamisk programmering kan du hitta några märkbara punkter. Värdet på ryggsäcksalgoritmen beror på två faktorer:
- Hur många paket övervägs
- Den återstående vikten som ryggsäcken kan lagra.
Därför har du två variabla kvantiteter.
Med dynamisk programmering har du användbar information:
- objektivfunktionen kommer att bero på två variabla storheter
- tabellen med alternativ kommer att vara en 2-dimensionell tabell.
Om anrop till B[i][j] är det högsta möjliga värdet genom att välja i paket {1, 2, …, i} med viktgräns j.
- Det maximala värdet när det väljs i n förpackningar med viktgränsen M är B[n][M]. Med andra ord: När det finns i-paket att välja är B[i][j] den optimala vikten när ryggsäckens maximala vikt är j.
- Den optimala vikten är alltid mindre än eller lika med den maximala vikten: B[i][j] ≤ j.
Till exempel: B[4][10] = 8. Det betyder att i det optimala fallet är den totala vikten av de valda paketen 8, när det finns 4 första paket att välja mellan (1:a till 4:e paketet) och maxvikten av ryggsäcken är 10. Det är inte nödvändigt att alla 4 föremålen är valda.
Formel för att beräkna B[i][j]
Ingång, du definierar:
- W[i], V[i] är i sin tur vikten och värdet av paket i, där i
![Formel för att beräkna B[i][j]](https://www.guru99.com/images/1/043019_0611_KnapsackPro4.png)
{1, …, n}. - M är den maximala vikt som ryggsäcken kan bära.
Om du helt enkelt bara har ett paket att välja på. Du beräknar B[1][j] för varje j: vilket betyder ryggsäckens maximala vikt ≥ vikten av det första paketet
B[1][j] = W[1]
Med viktgränsen j kommer de optimala valen bland paket {1, 2, …, i – 1, i} att ha det största värdet att ha två möjligheter:
- Om paket i inte är valt är B[i][j] det högsta möjliga värdet genom att välja bland paket {1, 2, …, i – 1} med viktgränsen j. Du har:
B[i][j] = B[i – 1][j]
- Om paket i väljs (betrakta givetvis endast detta fall när W[i] ≤ j) så är B[i][j] lika med värdet V[i] för paket i plus det maximala värdet kan erhållas genom att välja bland paket {1, 2, …, i – 1} med viktgräns (j – W[i]). Det vill säga när det gäller värdet du har:
B[i][j] = V[i] + B[i – 1][j – W[i]]
På grund av skapandet av B[i][j], vilket är det maximala möjliga värdet, kommer B[i][j] att vara maxvärdet av ovanstående 2 värden.
Grund för dynamisk programmering
Så du måste överväga om det är bättre att välja paket i eller inte. Därifrån har du den rekursiva formeln enligt följande:
B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]
Det är lätt att se B[0][j] = högsta möjliga värde genom att välja från 0 paket = 0.
Beräkna tabellen över alternativ
Du bygger en tabell med alternativ baserat på ovanstående rekursiva formel. För att kontrollera om resultaten är korrekta (om inte exakt, bygger du om objektivfunktionen B[i][j]). Genom att skapa objektivfunktionen B[i][j] och tabellen med alternativ, kommer du att orientera spårningen.
Tabell över alternativ B innehåller n + 1 rader, M + 1 kolumner,
- För det första, fylld med grunden för dynamisk programmering: Rad 0 inkluderar alla nollor.
- Använd rekursiva formler, använd rad 0 för att beräkna rad 1, använd rad 1 för att beräkna rad 2, etc. … tills alla linjer är beräknade.
Trace
När du beräknar tabellen med alternativ är du intresserad av B[n][M] som är det maximala värdet som erhålls när du väljer i alla n paket med viktgränsen M.
- If B[n][M] = B[n – 1][M] då är paket n inte valt, du spårar B[n – 1][M].
- If B[n][M] ≠ B[n – 1][M], märker du att det optimala urvalet har paketet n och spår B[n – 1][M – W[n]].
Fortsätt att spåra tills du når rad 0 i tabellen med alternativ.
Algoritm för att slå upp alternativtabellen för att hitta de valda paketen
Obs: Om B[i][j] = B[i – 1][j], väljs inte paketet i. B[n][W] är det optimala totala värdet av förpackningen som placeras i ryggsäcken.
Steg för spårning:
- steg 1: Från i = n, j = M.
- steg 2: Titta i kolumn j, upp från botten, hittar du linjen i så att B[i][j] > B[i – 1][j]. Markera valt paket i: Välj [i] = sant;
- steg 3: j = B[i][j] – W[i]. Om j > 0, gå till steg 2, annars gå till steg 4
- steg 4: Baserat på tabellen med alternativ för att skriva ut de valda paketen.
Java Koda
public void knapsackDyProg(int W[], int V[], int M, int n) {
int B[][] = new int[n + 1][M + 1];
for (int i=0; i<=n; i++)
for (int j=0; j<=M; j++) {
B[i][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= M; j++) {
B[i][j] = B[i - 1][j];
if ((j >= W[i-1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
}
System.out.print(B[i][j] + " ");
}
System.out.print("\n");
}
System.out.println("Max Value:\t" + B[n][M]);
System.out.println("Selected Packs: ");
while (n != 0) {
if (B[n][M] != B[n - 1][M]) {
System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
M = M - W[n-1];
}
n--;
}
}
Förklaring av Knapsack-koden:
- Skapa tabell B[][]. Ange standardvärde för varje cell är 0.
- Bygg tabell B[][] nedifrån och upp. Beräkna tabellen med alternativ med hämtningsformeln.
- Beräkna B[i][j]. Om du inte väljer paket i.
- Utvärdera sedan: om du väljer paket i kommer det att vara mer fördelaktigt än att återställa B[i][j].
- Spåra tabellen från rad n till rad 0.
- Om du väljer paket n. När du väl har valt paket n kan du bara lägga till vikt M – W[n – 1].
I den här handledningen har du två exempel. Här är java-kod för att köra ovanstående program med två exempel:
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{3, 4, 5, 9, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{3, 4, 4, 10, 4};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 11;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackDyProg(W, V, M, n);
}
Du har utgången:
- Första exemplet:
0 0 0 3 3 3 3 3 3 3 3 3 0 0 0 3 4 4 4 7 7 7 7 7 0 0 0 3 4 4 4 7 7 8 8 8 0 0 0 3 4 4 4 7 7 10 10 10 0 0 0 3 4 4 4 7 8 10 10 11 Max Value: 11 Selected Packs: Package 5 with W = 4 and Value = 4 Package 2 with W = 4 and Value = 4 Package 1 with W = 3 and Value = 3
- Andra exemplet:
0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15 Max Value: 15 Selected Packs: Package 5 with W = 4 and Value = 10 Package 4 with W = 1 and Value = 2 Package 3 with W = 1 and Value = 1 Package 2 with W = 2 and Value = 2
