Solving the knapsack problem via Z-transform

Given vectors $a,c\in Z^n$ and $b\in Z$, we consider the (unbounded) knapsack optimization problem $P:\,\min\{c'x\,\vert\, a'x=b;\,x\in N^n\}$. We compute the minimum value $p^*$ using techniques from complex analysis, namely Cauchy residue technique to integrate a function in $C^2$, the $Z$-transform of an appropriate function related to $P$. The computational complexity depends on $s:=\sum_{a_j} a_j$, not on the magnitude of $b$ as in dynamic programming based approaches. We also completely characterize the number of solutions with value less than $p$, as a function of $p$.


Operations Research Letters 30 (2002), 394-400