Answer Happy

**PLEASE SOLVE IT ON YOUR OWN AND DON'T COPY FROM
ANOTHER answers ANSWER UNLESS IT'S IDENTICAL OR -1**
Problem 3 (15 points) Here we consider a new version of the 0-1 knapsack problem studied in class. Again, there are N items, 11, 12, .., I., where item i has value v; and weight wi, and a number W. All numbers are positive integers. The goal is to collect a set of items that achieve the maximum value without exceeding the knapsack capacity W. In this new version of the problem, imagine that all items are connected to an alarm system which will be triggered if the thief picks up two consecutives items to put in his knapsack. So the added constraint now is: if you pick an item, you cannot pick any of its neighboring items. Show how to solve this problem using Dynamic Programming, Define OPT[i,j] to be the optimal value achieved if you consider only the first i items without exceeding capacity j. • (7 pts) Give a recursive solution to the problem by defining the sub-problems appropriately. Show the base case(s) as well (4 pts) Justify the correctness and use it to describe your DP algorithm. (4 pts) What is the time and space requirements needed by your algorithm? .