1. rugzakprobleem
1.1. het rugzak probleem is een probleem waarbij je iets hebt waar een maximaal aantal kg gewicht in kan. En je er spullen met waarde en gewicht in moet doen om zo veel mogelijk waarde te krijgen. als er bijvoorbeeld maximaal 20kg in een tas kan. dan moet je zoveel mogelijk met max 20 kg proberen te bereiken. hier is geen algoritme voor om het op te lossen.
1.1.1. omdat er geen algoritme voor is kan je 2 dingen doen
1.1.1.1. 1: je kan een algoritme maken dat alle mogelijkheden bij langs gaat. (een correct algoritme)
1.1.1.1.1. een algoritme dat alle mogelijkheden bij langs gaat noem je een bruteforce-algoritme. deze manier duurt heel lang. bij bijvoorbeeld 30 dozen heb je al meer dan 1 miljard mogelijkheden. het kan alleen handig zijn bij kleine problemen
1.1.1.2. 2: je kan een algoritme maken dat zo dicht mogelijk bij de oplossing in de buurt komt. (een efficiënt algoritme)
1.1.1.2.1. er zijn verschillende manieren om dit te doen je kan het bijvoorbeeld vereenvoudigen zodat je het snel en correct kan oplossen.
1.1.1.2.2. Een andere manier is het vinden van een willekeurige oplossing. Daarna probeert het algoritme het resultaat steeds te verbeteren met kleine aanpassingen. het algoritme stopt met zoeken als die een goed resultaat heeft gevonden
1.1.2. oplossing?
1.1.2.1. de wiskundige Dantzig het volgende algoritme bedacht:
1.1.2.1.1. stap 1: reken voor elke doos de waarde in kg uit