title: Knapzakprobleem
text: Het knapzakprobleem is een NP-volledig probleem in de wiskunde, informatica en cryptografie. Het knapzakprobleem komt van het volgende vraagstuk: 
  Gegeven een verzameling van objecten, elk met gewicht en waarde, bepaal welke (deel)verzameling van objecten meegenomen wordt in de knapzak, zodat het totale gewicht onder het maximum blijft en de totale waarde gemaximaliseerd wordt.
  
  Verschillende definities
  Er is de beschikking over objecten met gewicht  en een maximumgewicht . Vind nu een verzameling indices 
   met 
  
  Anderzijds is het probleem te formuleren als: vind een vector  van nullen en enen, met 
  
  Omdat het knapzakprobleem NP-Volledig is, bestaan er geen betere methoden om het probleem op te lossen, dan door alle  mogelijkheden voor  te proberen. Het is ook niet te voorspellen of een oplossing gevonden kan worden. Wel is het zo dat wanneer een oplossingsvector  is gevonden, deze in polynomiale tijd kan worden geverifieerd.
  
  Overige definities, inclusief waarde van objecten, zijn:
  
  Beperkt knapzakprobleem, waarin het nummer van elk object, , wordt beperkt tot een specifieke waarde, ,:
   Maximaliseer 
   zodat 
   met hierin  het aantal objecten. Elk object  heeft waarde  en gewicht . Het maximale gewicht dat kan worden meegenomen is 
  
  Onbeperkt knapzakprobleem, waarin er geen restricties zijn op de waarde van het nummer van elk object.
  
  Algoritmen
  Er is op dit moment geen algoritme bekend voor dit probleem dat:
   Altijd het juiste antwoord geeft en,
   Minder dan exponentiële tijd nodig heeft.
  
  Brute force
  Het brute force oplossen van dit probleem wil zeggen dat je alle mogelijk combinaties van objecten probeert en kijkt met welke combinatie van objecten je het beste resultaat krijgt. Hierbij wordt de zogenaamde machtsverzameling van de lijst van objecten gemaakt: de verzameling van alle deelverzamelingen.
  
  Greedy Algoritme
  Een greedy algoritme zou de objecten in aflopende volgorde sorteren aan de hand van de waarde/gewicht-verhouding van het object, en dan de objecten in deze volgorde in de knapzak stoppen tot er niets meer bij kan. Dit werkt, maar heeft als grote nadeel dat het ontzettend traag is voor wat grotere verzamelingen objecten.
  
    Sorteer de objecten op waarde/gewicht (w en g): w[1]/g[1]  w[2]/g[2]  w[3]/g[3]  ,,  w[n]/g[n]
    Neem S de lege verzameling; Gewicht = 0
  
    
    for i=1 to n
      if gewicht + g[i] <= G then
        Stop voorwerp i in S; gewicht += g[i]
      fi
    endfor
      
    Output S
  
  Bovenstaand algoritme werkt echter niet goed: 
  
  Neem als maximumgrootte van de knapzak de waarde G = 6 en de volgende twee voorwerpen: 
  
  g[1]= 1; w[1]=2 
  g[2]= 6; w[2]=6 
  
  Bovenstaand heuristiek geeft als oplossing dat de knapzak (met maximaal gewicht G van 6) slechts object 1 met waarde 2 bevat, terwijl de oplossing met object 2 met waarde 6 optimaal is: 
  
  Waarde/gewicht ratio van g[1] is: 2/1 = 2 
  Waarde/gewicht ratio van g[2] is: 6/6 = 1 
  Sorteren als: g[1], g[2] 
  
  Vervolgens zo veel mogelijk in de zak stoppen. 
  Na object 1 erin is er nog G - g[1] = 6 - 1 = 5 over voor andere objecten. 
  Object 2 past er niet meer in, dus stopt het algoritme. 
  
  Een mogelijk manier om dit te verbeteren is om te kijken of de waarden van alle objecten in S (de uitvoer van het algoritme) opgeteld minder is dan de waarde van het meest waardevolle element.
  
  In bovenstaand algoritme wordt het volgende vervangen:
  
    Output S
  
    if ( w[z] > W) then 
    Output z
    else 
    Output S
    fi
  
  W is hierin de opgetelde waarde van (de waarden van) de objecten in S, en z is het meest waardevolle element.
  
  Wanneer het algoritme op deze wijze wordt aangepast is de waarde van de oplossing altijd binnen een factor 2 van de optimale waarde.
  
  Dynamic Programming
  Bij het zogenaamde dynamic programming van het knapzakprobleem wordt in een tabel bijgehouden wat de beste knapzak is tot nu toe.
   tabel = een tabel van (1..n+1) bij (0..G)
   for w = 0..G
    tabel[n+1, w] = 0
   for i = n..1
    for w = 1..G
     if gewicht van object i <= w then 
      tabel[i,w] = max( tabel[i+1, w - gewicht object i] + waarde van object i, tabel[i+1, w] )
     else 
      tabel[i,w] = tabel[i+1, w]
     fi
   return tabel[1, G]
  Waarbij Objecten het lijstje van objecten is en G de maximale waarde van de knapzak. Dit algoritme gaat in de polynomiale tijd O(nG), wat in de limiet veel sneller is dan de theoretische exponentiële tijd. Maar het algoritme vereist dat de gewichten discreet zijn. Dit is dus geen oplossing voor het volledige theoretische probleem, maar in de praktijk kunnen de gewichten altijd afgerond worden om zo een oplossing tot op een zekere correctheid te vinden.
  
  Merkle en Hellman Trapdoor Knapsack methode 
  Het coderingssysteem van Merkle en Hellman is gebaseerd op een toepassing van het Knapzakprobleem. Het maakt gebruik van het idee dat het Knapzakprobleem in bepaalde gevallen makkelijk oplosbaar is. We noemen de vector  simpel als:
  
  Het coderingssysteem werkt dan als volgt:
   Genereer een aselecte enkelvoudige knapzakvector , deze blijft geheim.
   Genereer een aselect getal 
   en een aselect paar  met . 
  Dit kan snel via het uitgebreide algoritme van Euclides. Ook deze getallen worden geheimgehouden
   De public key is nu de vector 
  .
   Boodschappen worden gerepresenteerd als rijen binaire vectoren  van dezelfde lengte als  en 
  
  Voorbeeld: Als iemand  wil oversturen, pakt hij de publieke vector van de ontvanger, , en codeert deze als . Omdat  nu geen simpele vector meer is, vertrouwt men erop dat het  moeilijk decodeerbaar is door een afluisteraar.
  
  De ontvanger kan de boodschap decoderen door gebruik te maken van zijn geheime informatie,  en . Hiermee bepaalt hij 
   
  
  en kent dan ook 
  , want . 
  
  Hiermee kent hij , want  was simpel.
  
  Het systeem is echter niet meer bruikbaar omdat Adi Shamir in 1982 heeft aangetoond dat bij 1-staps codering bijna alles te kraken valt. De meertraps codering is in 1984 ook gekraakt.
  
  Referenties 
    Versie 1.2, pg.204.
  
  Cryptografie
  NP-volledig probleem