Knapsack problems¶
Part 2 of the course: chapters 2–9 of the lecture notes.
Lecture notes (PDF) Exercises (PDF)
-
2. DP for the 0/1 knapsack problem
Instances and feasible solutions · A first DP algorithm · A second DP algorithm
-
3. DP for the unbounded knapsack problem
Instances and feasible solutions · A first DP algorithm · A second DP algorithm
-
4. DP for the bounded knapsack problem
Instances and feasible solutions · A DP algorithm
-
5. DP for the subset sum problem
A DP algorithm
-
6. DP for the multiple-choice knapsack problem
A DP algorithm
-
7. DP for the multidimensional knapsack problem
A DP algorithm
-
8. DP for the knapsack problem with setups
A DP algorithm
-
9. DP for the multiple knapsack problem
A DP algorithm