🔗
- Linear programming – Wikipedia
🎥
- S.Devadas. Linear programming: LP, reductions, simplex – MIT OCW 6.046J: Design and analysis of algorithms (2015)
Dynamic programming is a method of solving optimization problems by breaking them into sub-problems and then recursively finding the optimal solutions to the sub-problems. All problems amenable to dynamic programming solution share the following two properties: optimal substructure (the optimal solution can be obtained given the optimal solutions of subproblems), and overlapping subproblems (sub-problems share sub-sub-problems).
🔗
- Dynamic programming – Wikipedia
- Weak NP-completeness – Wikipedia
❔
- Knapsack problem — NP-complete despite dynamic programming solution? – Computer Science
🎥
- Dynamic programming. Part I, Part II, Part III, Part IV – MIT 6.006: Introduction to algorithms (2011)
📖
- Ch. 8: Dynamic programming – S.S.Skiena. The algorithm design manual (2008)
Problem: partition (without reordering) a set of non-negative integral numbers into
kranges such that the maximum sum over all the ranges is minimized.
📝
- This problem has another solution based on binary searching the answer in the space of possible answers that is obtained using a greedy approach.
📖
- Sec. 8.5: The partition problem – S.S.Skiena. The algorithm design manual (2008)
- Sec. 8.4.1: Two components: Binary search the answer and other – S.Halim, F.Halim. Competitive programming (2013)