Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 122:
* If the total value of the optimal knapsack solution is at most 1, then we say that '''y''' is feasible.
* If the total value of the optimal knapsack solution is larger than 1, then we say that '''y''' is infeasible, and the items in the optimal knapsack solution correspond to a configuration that violates a constraint (since <math>\mathbf{a}\cdot \mathbf{y} > 1</math> for the vector '''a''' that corresponds to this configuration).
The knapsack problem can be solved by dynamic programming in pseudo-polynomial time: <math>O(n\cdot W)</math>, where ''n'' is the number of items and ''W'' is the number of different possible weights (for example, if all sizes are integers, then the runtime is <math>O(n\cdot B)</math>). If this is too slow, we can use an FPTAS for the knapsack problem.
=== Solving the fractional LP ===
| |||