Online knapzakprobleemoplosser

Maximaliseer de waarde binnen uw gewichtslimiet

Stel u voor dat u een rugzak heeft met een capaciteit van 5 kg en drie artikelen: A (2 kg, 6 punten), B (3 kg, 10 punten) en C (4 kg, 12 punten). U wilt de totale punten maximaliseren zonder meer dan 5 kg te dragen. Dit hulpmiddel berekent dat de optimale selectie A en B is, met een totale waarde van 16 punten en een totaal gewicht van 5 kg. C alleen zou 12 punten opleveren, maar A+B is beter.

Hoe het werkt

De oplosser gebruikt een dynamisch programmeringsalgoritme voor het 0/1-knapzakprobleem. Het gaat ervan uit dat elk artikel ondeelbaar is en maximaal één keer kan worden gekozen. Het algoritme evalueert alle combinaties binnen de opgegeven capaciteit en vindt de selectie met de hoogste totale waarde. De invoervereisten zijn strikt: gewichten moeten positieve gehele getallen zijn en mogen de capaciteit niet overschrijden; waarden mogen nul of positief zijn, tot 1 miljard.

Beperkingen

• Dit is geen fractioneel knapzakprobleem: u kunt geen deel van een artikel nemen.
• Het ondersteunt geen meerdere exemplaren van hetzelfde artikel (behalve door aparte regels met unieke namen).
• Het is niet multidimensionaal: er is slechts één gewichtsbeperking.
• Het is niet valuta-bewust: behandel waarden als abstracte scores, tenzij u uw eigen eenheden heeft genormaliseerd.
• Als er meerdere optimale oplossingen zijn, wordt er maar één gerapporteerd; er is geen garantie welke.

Veelgestelde vragen

Wat betekent 0/1 in de naam?

0/1 betekent dat elk artikel ofwel volledig wordt geselecteerd (1) ofwel helemaal niet (0). U kunt geen gedeeltelijke artikelen toevoegen, zoals bij een fractioneel knapzakprobleem.

Waarom krijg ik niet alle mogelijke optimale combinaties te zien?

Het hulpmiddel is ontworpen om één optimale selectie te tonen. Als er meerdere selecties dezelfde maximale waarde hebben, kiest het algoritme er één, maar het garandeert niet dat dit de lichtste of op een andere manier beste is. Voor besluitvorming moet u mogelijk zelf aanvullende criteria toepassen.

Kan ik negatieve waarden of gewichten invoeren?

Nee. Gewichten moeten positieve gehele getallen zijn (groter dan 0) en waarden moeten tussen 0 en 1.000.000.000 liggen. Negatieve waarden of gewichten worden niet geaccepteerd.