(the knapsack problem) – att packa en kappsäck med ett urval föremål ur ett större antal så att kappsäcken blir full, eller så full som möjligt. Föremålen är olika stora, och alla får inte plats. – Ett enkelt exempel är att kappsäcken har volymen 5 och föremålen har storlekarna 1, 2, 3, och 4. I så fall går det med 1+4 och 2+3. Det är enkelt, men om kappsäcken är större och föremålen många kan problemet bli omöjligt att lösa inom rimlig tid (ohanterligt). Det blir för många möjligheter att pröva. – Kappsäcksproblemet räknas som ett NP‑fullständigt problem. Det är ett optimeringsproblem som har praktisk tillämpning inom områden som transport.
[matematik och logik] [ändrad 2 maj 2017]