in de rugzak
Gewicht
Best mogelijk

    Voorwerpen

      Meer over het knapzakprobleem

      Knapzakprobleem

      Je kunt maar een bepaald gewicht dragen, en elk voorwerp heeft een gewicht en een waarde. Welke voorwerpen neem je mee om de meeste waarde te dragen? Elke combinatie proberen verdubbelt het werk met elk voorwerp. Een tabel met een rij per voorwerp en een kolom per capaciteit vindt de beste rugzak, cel voor cel. Tik op een voorwerp om het in de rugzak te stoppen, en tik er nog eens op (in de rugzak of op de plank) om het eruit te halen. De rugzak vult zich op gewicht, en de tegels tonen de dollars die je hebt ingepakt tegenover het best mogelijke. Druk op Best inpakken om de beste rugzak te zien. Verander in het paneel de kilo's en dollars van de voorwerpen, voeg voorwerpen toe of verwijder ze, en stel de capaciteit van de rugzak in. De weergave Tabel laat zien hoe dynamisch programmeren de beste rugzak vindt: druk op Afspelen om de tabel te zien vullen, of op Stap en Terug om één stap per keer te gaan, en sleep de stappenschuif om overal naartoe te springen. Elke rij voegt één voorwerp toe, elke kolom is een capaciteit in kilo, en elke cel bevat de meeste dollars die erin passen. Als de tabel geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.

      Hoe het werkt

      1. Tik op de dozen om ze in de rugzak te stoppen en zie hoe die zich vult op gewicht in kilo's.
      2. Probeer de best mogelijke waarde in dollars te halen, of druk op Best inpakken om de beste rugzak te zien.
      3. Open de weergave Tabel en druk op Afspelen om elke cel te zien kiezen tussen een voorwerp inpakken en laten liggen.

      Hoe de tabel werkt

      Elke rij voegt één voorwerp toe en elke kolom is een capaciteit van 0 tot die van de rugzak. Een cel bevat de hoogste waarde die in die capaciteit past met de voorwerpen tot en met haar rij. Zonder het nieuwe voorwerp is dat de cel erboven. Met het voorwerp, als het past, is het de waarde van het voorwerp plus de beste waarde voor het gewicht dat overblijft; die staat in de rij erboven, het gewicht van het voorwerp naar links. De cel houdt de grootste van de twee. De eerste rij, zonder voorwerpen, bestaat uit nullen.

      De voorwerpen teruglezen

      De cel rechtsonder is de beste waarde. Om de voorwerpen te vinden, begin je daar en vergelijk je die met de cel erboven: is die gelijk, dan was het laatste voorwerp niet nodig; is die groter, dan zit het voorwerp in de rugzak, dus trek je het gewicht ervan af en ga je naar die kolom. Ga elke keer een rij omhoog tot de eerste rij. De app toont dit teruglezen in oranje en zet de ingepakte voorwerpen onder de tabel.

      Veelgestelde vragen

      Wat betekent 0/1 in het 0/1-knapzakprobleem?

      Elk voorwerp wordt één keer ingepakt of helemaal niet, nooit gedeeltelijk en nooit twee keer. Als je voorwerpen kon verdelen, zoals rijstkorrels, dan was eerst de beste waarde per gewicht inpakken optimaal; dat is het fractionele knapzakprobleem.

      Waarom niet eerst de beste waarde per gewicht inpakken?

      Omdat hele voorwerpen gaten kunnen laten. Met een capaciteit van 7 en voorwerpen met gewicht 1, 3, 4 en 5 en waarde 1, 4, 5 en 7 heeft het voorwerp met gewicht 5 de beste waarde per gewicht, en daarnaast is alleen nog plaats voor het voorwerp met gewicht 1, samen 8. De voorwerpen met gewicht 3 en 4 zijn samen 9 waard.

      Hoe snel is het knapzakalgoritme?

      De tabel heeft (aantal voorwerpen + 1) maal (capaciteit + 1) cellen, en elke cel wordt in één stap gevuld. Dat is snel bij kleine capaciteiten, maar een capaciteit kan een enorm getal zijn, dus in het algemeen is het probleem NP-moeilijk; de tabelmethode heet pseudopolynomiaal.

      Kan hetzelfde voorwerp twee keer worden ingepakt?

      Hier niet. In het onbegrensde knapzakprobleem mag je elk voorwerp zo vaak nemen als je wilt; de tabel leest dan de cel links in dezelfde rij in plaats van de rij erboven, zoals in de app over wisselgeld.

      Wordt er iets verstuurd?

      Nee. Alles wordt in je browser berekend, en je laatste instellingen blijven in de lokale opslag van deze browser.

      Klaar om het te proberen?

      Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

      Ga naar Editor