streamalism.org

1. Inleiding

Het knapzakprobleem is een combinatorisch optimalisatieprobleem dat vele toepassingen kent. In deze tutorial lossen we dit probleem op in Java.

2. Het knapzakprobleem

In het knapzakprobleem hebben we een aantal items. Elk item heeft een gewicht en een waarde:

We willen deze items in een rugzak stoppen. Het heeft echter een maximumgewicht:

Daarom moeten we de items kiezen waarvan het totale gewicht de gewichtslimiet niet overschrijdt, en hun totale waarde is zo hoog mogelijk. De beste oplossing voor het bovenstaande voorbeeld is bijvoorbeeld om het artikel van 5 kg en het artikel van 6 kg te kiezen, wat een maximale waarde van $ 40 oplevert binnen de gewichtslimiet.

Het knapzakprobleem kent verschillende variaties. In deze tutorial zullen we ons concentreren op het probleem met de 0-1 knapzak. In het 0-1 knapzakprobleem moet elk item worden gekozen of achtergelaten. We kunnen geen deel van een artikel afnemen. Ook kunnen we een item niet meerdere keren meenemen.

3. Wiskundige definitie

Laten we nu het 0-1 knapzakprobleem formaliseren in wiskundige notatie. Gegeven een set van n items en het gewichtslimiet W.kunnen we het optimalisatieprobleem definiëren als:

Dit probleem is NP-moeilijk. Daarom is er momenteel geen polynoom-tijd-algoritme om het op te lossen. Er is echter een pseudo-polynoom tijdalgoritme dat dynamische programmering gebruikt voor dit probleem.

4. Recursieve oplossing

We kunnen een recursieformule gebruiken om dit probleem op te lossen:

In deze formule M (n, w) is de optimale oplossing voor n artikelen met een gewichtslimiet w. Het is het maximum van de volgende twee waarden:

• De optimale oplossing van (n-1) items met een maximumgewicht w (exclusief de n-de item)
• Waarde van de n-de item plus de optimale oplossing van (n-1) items en w minus gewicht van de n-de item (inclusief de n-de item)

Als het gewicht van de n-de item is meer dan de huidige gewichtslimiet, we nemen het niet op. Daarom valt het in de eerste categorie van de bovenstaande twee gevallen.

We kunnen deze recursieformule in Java implementeren:

int knapsackRec (int [] w, int [] v, int n, int W) {if (n W) {retourneer knapsackRec (w, v, n - 1, W); } else {return Math.max (knapsackRec (w, v, n - 1, W), v [n - 1] + knapsackRec (w, v, n - 1, W - w [n - 1])); }} 

Bij elke recursiestap moeten we twee suboptimale oplossingen evalueren. Daarom is de looptijd van deze recursieve oplossing O (2n).

5. Dynamische programmeeroplossing

Dynamisch programmeren is een strategie voor het lineariseren van anders exponentieel moeilijke programmeerproblemen. Het idee is om de resultaten van deelproblemen op te slaan, zodat we ze later niet opnieuw hoeven te berekenen.

We kunnen het 0-1 knapzakprobleem ook oplossen met dynamisch programmeren. Om dynamisch programmeren te gebruiken, maken we eerst een 2-dimensionale tabel met afmetingen van 0 tot n en 0 tot W.. Vervolgens gebruiken we een bottom-up benadering om met deze tabel de optimale oplossing te berekenen:

int knapsackDP (int [] w, int [] v, int n, int W) {if (n <= 0 || W <= 0) {return 0; } int [] [] m = nieuwe int [n + 1] [W + 1]; voor (int j = 0; j <= W; j ++) {m [0] [j] = 0; } for (int i = 1; i <= n; i ++) {for (int j = 1; j j) {m [i] [j] = m [i - 1] [j]; } anders {m [i] [j] = Math.max (m [i - 1] [j], m [i - 1] [j - w [i - 1]] + v [i - 1]); }}} retourneer m [n] [W]; } 

In deze oplossing hebben we een geneste lus over het itemnummer n en de gewichtslimiet W.. Daarom is het looptijd O (nW).

6. Conclusie

In deze tutorial hebben we een wiskundige definitie van het 0-1 knapzakprobleem laten zien. Vervolgens hebben we een recursieve oplossing voor dit probleem met Java-implementatie geboden. Ten slotte hebben we dynamische programmering gebruikt om dit probleem op te lossen.

Zoals altijd is de broncode voor het artikel beschikbaar op GitHub.