Partial 2 Homework 1 Solution

Knapsack Problem




Given n items of known weights **w**₁, ...,**w**n and values **v**₁, ..., **v**n and

a knapsack of capacity **W**, find the most valuable subset of the items that fit into the knapsack.




- Implement the recursive algorithm to solve the knapsack problem discussed in class.




- Approximate its time complexity utilizing the heuristic method.




- Can you determine its time complexity with another method?




---