Which of the following problems is equivalent to the 0-1 Knapsack problem?a.You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum valueb.You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximizedc.You are given a suitcase that can carry a maximum weight of 15kg. You are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum valued.You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the minimum number of coins required to get the sum S

Question1Max. score: 100.000/1 Knapsack ProblemYou are given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Note that we have only one quantity of each item.In other words, given two integer arrays val[0..N-1] and wt[0..N-1] which represent values and weights associated with N items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).Input:First Line Containf the size of the itemsSecond line contains Profit valuesThird Line Contains Weights Fourth line contains Capacity Output:  Output=Max ProfitExample 1:Input:31 2 34 5 1 3Output: 3

Given weights and values of N items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.Note: Unlike 0/1 knapsack, you are allowed to break the item here.

Solve the following instance of greedy knapsack problem where n=4, m=10, p = (40, 42, 25,12) and w = (4, 7, 5, 3)

ou are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

Which of the following problems is NOT solved using dynamic programming? 0/1 knapsack problem Matrix chain multiplication problem Edit distance problem  Fractional knapsack problem