în rucsac
Greutate
Cel mai bun posibil

    Obiecte

      Mai multe despre problema rucsacului

      Problema rucsacului

      Puteți căra doar o anumită greutate, iar fiecare obiect are o greutate și o valoare. Ce obiecte luați ca să cărați cea mai mare valoare? Încercarea tuturor combinațiilor dublează munca la fiecare obiect. Un tabel cu un rând pentru fiecare obiect și o coloană pentru fiecare capacitate găsește cel mai bun rucsac celulă cu celulă. Atingeți un obiect ca să-l puneți în rucsac și atingeți-l din nou (în rucsac sau pe raft) ca să-l scoateți. Rucsacul se umple după greutate, iar casetele arată dolarii puși în rucsac comparativ cu cel mai bun rezultat posibil. Apăsați Cea mai bună încărcare ca să vedeți cel mai bun rucsac. În panou puteți schimba kilogramele și dolarii obiectelor, puteți adăuga sau elimina obiecte și puteți seta capacitatea rucsacului. Vizualizarea Tabel arată cum găsește programarea dinamică cel mai bun rucsac: apăsați Redare ca să vedeți cum se umple tabelul, sau Pas și Înapoi ca să mergeți câte un pas, și trageți glisorul de pași ca să săriți oriunde. Fiecare rând adaugă un obiect, fiecare coloană este o capacitate în kilograme, iar fiecare celulă conține cei mai mulți dolari care încap. Când tabelul este selectat, tastele săgeți merg câte un pas, bara de spațiu pornește și pune pe pauză redarea, iar Home și End sar la început și la sfârșit.

      Cum funcționează

      1. Atingeți cutiile ca să le puneți în rucsac și urmăriți cum se umple după greutatea în kilograme.
      2. Încercați să atingeți cea mai bună valoare posibilă în dolari sau apăsați Cea mai bună încărcare ca să vedeți rucsacul cel mai bun.
      3. Deschideți vizualizarea Tabel și apăsați Redare ca să vedeți cum fiecare celulă alege între a pune și a lăsa un obiect.

      Cum funcționează tabelul

      Fiecare rând adaugă un obiect, iar fiecare coloană este o capacitate de la 0 până la cea a rucsacului. O celulă conține cea mai mare valoare care încape în acea capacitate folosind obiectele până la rândul ei. Fără obiectul nou, aceasta este celula de deasupra. Cu el, dacă încape, este valoarea obiectului plus cea mai bună valoare pentru greutatea rămasă, care se află în rândul de deasupra, cu atâtea coloane mai la stânga cât cântărește obiectul. Celula o păstrează pe cea mai mare dintre cele două. Primul rând, fără obiecte, conține numai zerouri.

      Reconstituirea obiectelor

      Celula din dreapta jos este cea mai bună valoare. Ca să găsiți obiectele, porniți de acolo și comparați-o cu celula de deasupra: dacă este la fel, ultimul obiect nu a fost necesar; dacă este mai mare, obiectul este în rucsac, așa că scădeți greutatea lui și mergeți la acea coloană. Urcați de fiecare dată un rând, până la primul rând. Aplicația arată această reconstituire cu portocaliu și listează obiectele din rucsac sub tabel.

      Întrebări frecvente

      Ce înseamnă 0/1 în problema rucsacului 0/1?

      Fiecare obiect este pus în rucsac o dată sau deloc, niciodată parțial și niciodată de două ori. Dacă obiectele ar putea fi tăiate, precum boabele de orez, ar fi optim să puneți întâi cea mai bună valoare pe unitatea de greutate; aceasta este problema fracționară a rucsacului.

      De ce să nu puneți întâi cea mai bună valoare pe unitatea de greutate?

      Pentru că obiectele întregi pot lăsa goluri. Cu o capacitate de 7 și obiecte cu greutățile 1, 3, 4 și 5 și valorile 1, 4, 5 și 7, cea mai bună valoare pe unitatea de greutate o are obiectul cu greutatea 5, care lasă loc doar pentru obiectul cu greutatea 1, în total 8. Obiectele cu greutățile 3 și 4 valorează împreună 9.

      Cât de rapid este algoritmul rucsacului?

      Tabelul are (numărul de obiecte + 1) ori (capacitatea + 1) celule, fiecare completată într-un pas. Este rapid pentru capacități mici, dar o capacitate poate fi un număr uriaș, așa că, în general, problema este NP-dificilă; metoda tabelului se numește pseudopolinomială.

      Poate fi pus același obiect de două ori?

      Nu aici. În problema rucsacului nemărginită, fiecare obiect poate fi luat de oricâte ori; tabelul citește atunci celula din stânga de pe același rând în loc de rândul de deasupra, ca în aplicația despre restul de bani.

      Este trimis ceva undeva?

      Nu. Totul este calculat în browserul dumneavoastră, iar ultimele setări rămân în spațiul de stocare local al acestui browser.

      Ești gata să încerci?

      Deschide PictorX în browser – fără instalare și fără card de credit.

      Mergi la editor