Online løser for rygsækproblemet

Forståelse af 0/1-rygsækproblemet

0/1-rygsækproblemet handler om at vælge en delmængde af genstande, så den samlede vægt ikke overstiger en given kapacitet, og den samlede værdi maksimeres. Hver genstand kan enten vælges eller ikke vælges (0/1). Dette værktøj løser problemet præcist ved hjælp af dynamisk programmering.

Eksempel med konkrete data

Antag følgende genstande:

• A: vægt 2, værdi 6
• B: vægt 3, værdi 10
• C: vægt 4, værdi 12

Med en kapacitet på 5 er den maksimale værdi 16, og de valgte genstande er A og B. Dette kan du selv afprøve i værktøjet.

Begrænsninger og inputregler

• Genstandsnavne skal være ikke-tomme og unikke.
• Vægten skal være et positivt heltal, der ikke overstiger kapaciteten.
• Værdien kan være fra 0 til 1.000.000.000.
• Antal genstande: mellem 1 og 200.
• Kapacitet: heltal fra 1 til 5000.

Bemærk, at dette værktøj ikke understøtter fraktionelle genstande, flere eksemplarer af samme genstand, flere dimensioner eller valutaomregning. Værdier behandles som abstrakte tal, medmindre du selv har normaliseret dem.

Ofte stillede spørgsmål

Hvordan vælger løseren mellem flere optimale løsninger?

Løseren returnerer kun én optimal løsning. Hvis flere kombinationer giver samme maksimale værdi, er der ingen garanti for, hvilken der vises, og der tages ikke hensyn til sekundære kriterier som lavest vægt.

Kan jeg indtaste genstande med decimaltal for vægt?

Nej, vægten skal være et positivt heltal. Værdien kan dog være et heltal op til 1.000.000.000.

Hvad sker der, hvis jeg indtaster en genstand med vægt større end kapaciteten?

En sådan genstand kan aldrig vælges, da den overskrider kapaciteten. Løseren accepterer den, men den vil ikke indgå i nogen optimal løsning.