03: In the 0-1 Knapsack problem, we are given two things. First a list of n items (v1, wl)412. w2)...(vn, wn), where item i has value vi and weight wi. Second a weight W which is the maximum weight that can be carried in the knapsack. The items are indivisible so that we must either place the entire item in the knapsack or not place it in the knapsack. Our goal is to maximize the sum of the values of all the items that are placed in the knapsack. Part 1: Professor Clyde claims that a greedy algorithm will solve this problem. Is he correct? If yes, analyze and evaluate the profit. (CO3,41 L-4,6|(10 Marks)
Answers
Answered by
2
In the 0-1 Knapsack problem, we are given two things. First a list of n items (v1, wl)412. w2)...(vn, wn), where item i has value vi and weight wi. Second a weight W which is the maximum weight that can be carried in the knapsack. The items are indivisible so that we must either place the entire item in the knapsack or not place it in the knapsack. Our goal is to maximize the sum of the values of all the items that are placed in the knapsack. Part 1: Professor Clyde claims that a greedy algorithm will solve this problem. Is he correct? If yes, analyze and evaluate the profit. (CO3,41 L-4,6|(10 Marks)
Similar questions