i ryggsäcken
Vikt
Bästa möjliga

    Föremål

      Mer om kappsäcksproblemet

      Kappsäcksproblemet

      Du kan bara bära en viss vikt, och varje föremål har en vikt och ett värde. Vilka föremål tar du med för att bära mest värde? Att pröva varje kombination fördubblar arbetet för varje föremål. En tabell med en rad per föremål och en kolumn per kapacitet hittar den bästa ryggsäcken en cell i taget. Tryck på ett föremål för att lägga det i ryggsäcken, och tryck på det igen (i ryggsäcken eller på hyllan) för att ta ut det. Ryggsäcken fylls efter vikt, och rutorna visar dollarna du har packat jämfört med bästa möjliga. Tryck på Bästa packning för att se den bästa ryggsäcken. I panelen kan du ändra föremålens kilo och dollar, lägga till eller ta bort föremål och ställa in ryggsäckens kapacitet. Vyn Tabell visar hur dynamisk programmering hittar den bästa ryggsäcken: tryck på Spela för att se tabellen fyllas, eller på Steg och Bakåt för att gå ett steg i taget, och dra stegreglaget för att hoppa vart som helst. Varje rad lägger till ett föremål, varje kolumn är en kapacitet i kilo, och varje cell innehåller flest dollar som får plats. När tabellen är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

      Hur det fungerar

      1. Tryck på lådorna för att packa dem i ryggsäcken och se den fyllas efter vikt i kilo.
      2. Försök nå bästa möjliga värde i dollar, eller tryck på Bästa packning för att se den bästa ryggsäcken.
      3. Öppna vyn Tabell och tryck på Spela för att se varje cell välja mellan att packa och lämna ett föremål.

      Så fungerar tabellen

      Varje rad lägger till ett föremål och varje kolumn är en kapacitet från 0 upp till ryggsäckens. En cell innehåller det största värdet som får plats i den kapaciteten med föremålen till och med dess rad. Utan det nya föremålet är det cellen ovanför. Med det, om det får plats, är det föremålets värde plus bästa värdet för vikten som är kvar, som står i raden ovanför, föremålets vikt åt vänster. Cellen behåller det större av de två. Den första raden, utan föremål, är bara nollor.

      Läsa bakåt fram föremålen

      Cellen längst ned till höger är bästa värdet. För att hitta föremålen börjar du där och jämför med cellen ovanför: om den är densamma behövdes inte det sista föremålet; om den är större ligger föremålet i ryggsäcken, så dra bort dess vikt och gå till den kolumnen. Gå upp en rad varje gång tills du når den första raden. Appen visar bakåtläsningen i orange och listar de packade föremålen under tabellen.

      Ofta ställda frågor

      Vad betyder 0/1 i 0/1-kappsäcksproblemet?

      Varje föremål packas en gång eller inte alls, aldrig delvis och aldrig två gånger. Om föremålen kunde delas, som riskorn, vore det optimalt att packa bästa värdet per vikt först; det är det fraktionella kappsäcksproblemet.

      Varför inte packa bästa värdet per vikt först?

      Eftersom hela föremål kan lämna luckor. Med kapaciteten 7 och föremål med vikterna 1, 3, 4 och 5 som är värda 1, 4, 5 och 7 har föremålet med vikt 5 bäst värde per vikt, och då finns det bara plats för föremålet med vikt 1, totalt 8. Föremålen med vikt 3 och 4 är tillsammans värda 9.

      Hur snabb är algoritmen för kappsäcksproblemet?

      Tabellen har (antal föremål + 1) gånger (kapacitet + 1) celler, och varje cell fylls i ett steg. Det går snabbt för små kapaciteter, men en kapacitet kan vara ett enormt tal, så i allmänhet är problemet NP-svårt; tabellmetoden kallas pseudopolynomiell.

      Kan samma föremål packas två gånger?

      Inte här. I det obegränsade kappsäcksproblemet kan varje föremål tas hur många gånger som helst; tabellen läser då cellen till vänster i samma rad i stället för raden ovanför, som i appen om växelpengar.

      Skickas något någonstans?

      Nej. Allt räknas ut i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

      Redo att prova det?

      Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

      Gå till Editor