Be sure to include Algorithm description paragraph or pseud

5. Santa needs some help For this problem imagine you are Santa and you want to try to perfectly pack your sleigh with presents. That is, you want to pack up the sleigh with some of the presents from the workshop so that the total weight of the presents on the sleigh is exactly equal to the capacity of the sleigh, no more, no less Formally, the problem is as follows: Perfect Christmas Packing Problem: Input Christmas presents, each with weight wi We, wn A positive integer k denoting the maximum weight santo\'s sleigh can hold. output: output yes if there is a subset of the n presents whose total weight sums to exactly k output no if there is no such subset. Design a onk) run-time algorithm to solve this problem.

Solution

ALGORITHM FOR SANTY WEIGH PROBLEM

/*

input values:
Values results [array v]
Weights array (w)
total items (n)
santy bag capacity (K)
*/

for j from 0 to K do:
p[0, j] := 0
  
for i from 1 to n do:
for j from 0 to K do:
if w[i] > j then:
p[i, j] := p[i-1, j]
else:
p[i, j] := max(p[i-1, j], p[i-1, j-w[i]] + v[i])
          
          
--------------------------------------------------------------------------
This solution takes O(nK) time and O(nK) space.