GRE Computer Science Question 57

57. A hiker faces the 0/1 Knapsack problem. There are 7 items to be packed into the knapsack, each with value vi and weight wi as shown in the following table. i 1 2 3 4 5 6 7 vi 3 6 8 1 2 5 7 wi 7 3 5 1 4 2 6 The knapsack, which is initially empty, can hold a maximum weight of 24, so some item(s) must be left behind, and fractions of items cannot be packed. The optimality criterion is to maximize the total value of the items that are placed in the knapsack. The hiker fills the knapsack one item at a time, using a heuristic algorithm that is greedy on value density, where the value density of an item is its value/weight ratio. When this heuristic algorithm is used, what is the total value of the items that are packed, and is this total optimal? Total Value Optimal/Not Optimal (A) 29 Optimal (B) 29 Not optimal (C) 30 Optimal (D) 30 Not optimal (E) 32 Optimal