Given n items where each item i has weight w i and value v i $,$ a knapsack with capacity W $,$ and a target value

V $.$ Give an algorithm that determines if there exists a subset of items that fits within the capacity and has a total

value of exactly V $.$ Prove formally that your algorithm is correct. Describe the running time, with full points for a

polynomial running time.

Inputs:

$$ An integer n representing the number of items

$$ Arrays w$[1..$n$]$ and v$[1..$n$]$ representing the item weights and values

$$ An integer W representing knapsack capacity

$$ An integer V representing target value

Outputs:

$$ true if such a subset exists or false if otherwise.