Knapsack Optimization with Python
Vložit
- čas přidán 8. 09. 2024
- The purpose of the knapsack problem is to select which items to fit into the bag without exceeding a weight limit of what can be carried. We solve the problem with an integer programming solver (APOPT) by setting up each item as a binary variable (0 or 1).
📙 Knapsack Optimization: apmonitor.com/...
Objective: Maximize the value of items that can fit into a knapsack without exceeding a maximum weight constraint.
There are 4 items available to be placed in a knapsack: a towel, hammer, wrench, and screwdriver. The value and weight of the items are listed in the table below.
Towel Hammer Wrench Screwdriver
Item Value (vi) 11 8 3 6
Item Weight (wi) 3 5 7 4
Very good classroom, thanks Professor
Helped me a lot! Thanks for sharing this amazing content :)
proff, is this mixed integer solution taking linear time for selecting the items needed?
the greedy one takes n logn as we have to sort and then take the ones needed
I’m not sure there is a deterministic scale up factor proven for mixed integer linear programming. The solution speed often depends on tuning parameters, such as gap tolerance.
Professor do you see that I’m in necessity to learn MATLAB as I used to use python
Python is a powerful tool, but you can also think of it as a Matlab toolbox. Here is a tutorial on calling Python from Matlab: apmonitor.com/che263/index.php/Main/MatlabCallsPython