On equivalent knapsack problems (Q1082265): Difference between revisions

By aggregating objective function and constraint of a knapsack problem max\(\{\) c'x\(|\) a'x\(\leq b\), \(x\geq 0\) integral\(\}\) an equivalent problem of the following form is obtained: Let \(t=[c_ 1b/a_ 1]+1\) and let \(F(z)=\min \{(c+ta)'x|\) c'x\(\equiv z mod t\), \(x\geq 0\), integral\(\}\). Then z is an optimal value of the given problem if it is maximal subject to \(0\leq z<t\) and \(z+tb\geq F(z)\). Such a value z can be determined by dynamic programming with recursion: \(F(z)=\min_{j}(c_ j+ta_ j+F(z-c_ j))\). This procedure can be speeded up by calculating a recursion only for the values \(1,2,...,c_ 1-1\). Since the classical recursions use computation modulo \(a_ 1\), the new method might be advantageous if \(c_ 1<a_ 1\).