The following is known as the KNAPSACK problem. You have a knapsack and a collection of...

  

Transcribed Image Text:

The following is known as the KNAPSACK problem. You have a knapsack and a collection of valuable objects. Each object O has a weight O.W and a value O.V. There is a m on the total weight that you can carry. You have a target value T. The question is, can you choose objects to pack so that their total value is at least T and their total weigh M. For instance, suppose that T = 20, M = 10 and you have the following objects Object ABCDE Value 108764 Weight 8 4331 The only solution here is {B,C,D } with a total value of 21 and a total weight of 10. Note that the solution includes neither the most valuable item (A) nor the item with the value per weight (E). Consider the following state space solution. Assume that the objects have names that can be listed alphabetically. A state is an alphabetical list of the objects with a total weight at most M. For instance [C] is one state; [B,E] is another state. Given a state L, an operator on L is to add an object O at the end of L. To preserve the alphabetical order, O must be alphabetically later than the last element in L. T weight must be less than M. For instance, the operators on the state [C] are to add D, forming [C,D] or to add E forming [C,E]. The start state is the empty list. A state satisfies the goal if the total value is at least T. A. Show the complete state space for the above example. B. Suppose that you use a depth-first search to explore the state space. Which of the states in (A) will you generate, and in what order? C. Suppose that you use a breadth-first search to explore the state space. Which of the states in (A) will you generate, and in what order? The following is known as the KNAPSACK problem. You have a knapsack and a collection of valuable objects. Each object O has a weight O.W and a value O.V. There is a m on the total weight that you can carry. You have a target value T. The question is, can you choose objects to pack so that their total value is at least T and their total weigh M. For instance, suppose that T = 20, M = 10 and you have the following objects Object ABCDE Value 108764 Weight 8 4331 The only solution here is {B,C,D } with a total value of 21 and a total weight of 10. Note that the solution includes neither the most valuable item (A) nor the item with the value per weight (E). Consider the following state space solution. Assume that the objects have names that can be listed alphabetically. A state is an alphabetical list of the objects with a total weight at most M. For instance [C] is one state; [B,E] is another state. Given a state L, an operator on L is to add an object O at the end of L. To preserve the alphabetical order, O must be alphabetically later than the last element in L. T weight must be less than M. For instance, the operators on the state [C] are to add D, forming [C,D] or to add E forming [C,E]. The start state is the empty list. A state satisfies the goal if the total value is at least T. A. Show the complete state space for the above example. B. Suppose that you use a depth-first search to explore the state space. Which of the states in (A) will you generate, and in what order? C. Suppose that you use a breadth-first search to explore the state space. Which of the states in (A) will you generate, and in what order?