Question

Design a dynamic programming algorithm for the version of the knapsack problem in which there are unlimited quantities of copies for each of the n item kinds given. Indicate the time efficiency of the algorithm

Answer 1

The pseudocode is given as:

PSEUDOCODE:
function UnboundedKnapsack(capacity, n, weights, vals)
dp = []
for i = 0 to capacity do
dp.append(0)

end loop
for i = 0 to capacity do
for j = 0 to n-1 do
if weight[j] < i then
dp[i] = max(dp[i] , dp[i-weight[j]]+val[j])

end if

end loop

end loop
return dp[Capacity]
end function

Time complexity: Θ((W+1)*N).