Given vectors a,c∈ℤn and b∈ℤ, we consider the (unbounded) knapsack optimization problem ℙ: min{c′x|a′x=b; x∈ℕn}. We compute the minimum value p* using techniques from complex analysis, namely Cauchy's Residue Theorem to integrate a function in ℂ2, and the ℤ-transform of an appropriate function related to ℙ. The computational complexity depends on s:=Σj=1naj, 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.
