Given vectors a,c@?Z^n and b@?Z, we consider the (unbounded) knapsack optimization problem P:min{c'x|a'x=b;x@?N^n}. We compute the minimum value p^* using techniques from complex analysis, namely Cauchy's Residue Theorem to integrate a function in C^2, and the Z-transform of an appropriate function related to P. The computational complexity depends on s@?@?"j"="1^na"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.
['Jean B. Lasserre', 'Eduardo S. Zeron']
Solving the knapsack problem via Z-transform