Menu
Why isn't the knapsack problem included under the category of linear programming algorithms in spite of the fact that the Knapsack problem statement seems similar to the problems in linear programming?
363
The 0/1 knapsack problem is solved by the dynamic programming.
Greedy algorithm. A greedy algorithm is the most straightforward approach to solving the knapsack problem, in that it is a one-pass algorithm that constructs a single final solution.
The basic idea of Knapsack dynamic programming is to use a table to store the solutions of solved subproblems. If you face a subproblem again, you just need to take the solution in the table without having to solve it again. Therefore, the algorithms designed by dynamic programming are very effective.
In contrast to linear programming, a dynamic programming formulation does not require any linearity assumptions. Consequently, the method is applicable to a wider range of problems. This versatility is certainly quite welcome.
Knapsack can be written as an integer linear programming program. Unlike normal linear programming, this problem requires that variables in the solution are integers. Linear programming is known to be solvable in polynomial time, while integer linear programming is NP-complete.
Exercise for the reader: show that 3SAT can be reduced to integer linear programming.
Trivia: there are approximation algorithms for problems such as MAX-3SAT (a variant of 3SAT where we want to maximize the number of satisfied clauses). First you write MAX-3SAT as an integer linear program. Then, you relax it to linear program, by removing the integer restriction. Then, you solve the linear program in polynomial time. Finally, given real xi ∈ [0,1], you round them to integers, or generate random integer solution yi where probability of yi = 1 is xi.
153
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
