An extension of a greedy heuristic for the knapsack problem (Q1178644): Difference between revisions

A new heuristic for the knapsack problem which may be formulated in the following way is analyzed: Find nonnegative integers \(x_ 1,\dots,x_ n\) such that \(a_ 1x_ 1+\cdots+a_ nx_ n\leq b\) and \(p_ 1x_ 1+\cdots+p_ nx_ n\) is maximized where \(p_ 1/a_ 1\geq p_ 2/a_ 2\geq\cdots\geq p_ n/a_ n\). This heuristic \(H_ 2\) gets the maximal value by allocating \(b\) only to activities 1, 2 with, perhaps, some residual. The residual is then allocated to activities 3, 4 in an optimal manner, leaving, perhaps, a residual, etc. It extends the well-known greedy heuristic \(H_ 1\) which first allocates activity 1 in an optimal way, then activity 2, etc. It is shown that neither one of these two heuristics dominates the other. Furthermore, the performance of \(H_ 2\) is analyzed and necessary and sufficient conditions for \(H_ 2\) to be optimal are given.