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 … Read more