Innehåll
- Definition - Vad betyder ryggsäckproblem?
- En introduktion till Microsoft Azure och Microsoft Cloud | I hela denna guide kommer du att lära dig vad cloud computing handlar om och hur Microsoft Azure kan hjälpa dig att migrera och driva ditt företag från molnet.
- Techopedia förklarar knapsäckproblem
Definition - Vad betyder ryggsäckproblem?
Ryggsäckproblemet är ett optimeringsproblem som används för att illustrera både problem och lösning. Det härleder sitt namn från ett scenario där man är begränsad i antalet objekt som kan placeras i en ryggsäck i fast storlek. Med en uppsättning föremål med specifika vikter och värden är målet att få så mycket värde i ryggsäcken som möjligt med tanke på ryggsäckens viktbegränsning.
En introduktion till Microsoft Azure och Microsoft Cloud | I hela denna guide kommer du att lära dig vad cloud computing handlar om och hur Microsoft Azure kan hjälpa dig att migrera och driva ditt företag från molnet.
Techopedia förklarar knapsäckproblem
Ryggsäckproblemet är ett exempel på ett kombinerande optimeringsproblem, ett ämne i matematik och datavetenskap om att hitta det optimala objektet bland en uppsättning objekt. Detta är ett problem som har studerats i mer än ett sekel och är ett vanligt använt exempelproblem i kombinatorisk optimering, där det finns ett behov av ett optimalt objekt eller en begränsad lösning där en uttömmande sökning inte är möjlig. Problemet finns i verkliga scenarier som resursallokering i finansiella begränsningar eller till och med vid val av investeringar och portföljer. Det finns också inom områden som tillämpad matematik, komplexitetsteori, kryptografi, kombinatorik och datavetenskap. Det är lätt det viktigaste problemet inom logistik.
I ryggsäckproblemet har de givna artiklarna minst två attribut - ett objekts värde, som påverkar dess betydelse, och ett objekts vikt eller volym, vilket är dess begränsningsaspekt. Eftersom en uttömmande sökning inte är möjlig kan man dela problemen i mindre delproblem och köra det rekursivt. Detta kallas en optimal understruktur. Det handlar bara om en artikel åt gången och den aktuella vikten finns fortfarande tillgänglig i ryggsäcken. Problemlösaren behöver bara bestämma om produkten ska tas eller inte baserat på vikten som fortfarande kan accepteras. Om det är ett program är omberäkningen emellertid inte oberoende och skulle orsaka problem. Det är här som dynamiska programmeringstekniker kan tillämpas. Lösningar för varje delproblem lagras så att beräkningen bara skulle behöva ske en gång.