algorithms

11. In the Knapsack problem we have seen in class the input is an array A with the sizes of n items, and integer K which is the size of the knapsack. Consider the following versions of the problem: (a) In this version assume that each item is infinitely available, i.e. given a size A[i] we can pick any number of items with that size to put in the knapsack. Design an algorithm based on dynamic programming to determine whether it is possible to pack the knapsack fully or not. (b) [10pts] The problem is the same as the previous one (part-a), except now each item has an associated value also. Design an algorithm to find how to pack the knapsack fully, such that the items in it have the maximal value among all possible ways to fully pack the knapsack. 4. [10pts] Construct a sample connected undirected graph with 7 vertices and 11 edges. Run DFS on your graph, number the vertices with the DFS numbers and construct the DFS tree of your traversal. Show the DFS tree edges and back edges on your graph