Assigned: Feb. 11
Due: Feb. 18
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 maximum 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 weight is at most
M.
For instance, suppose that T = 20, M = 10 and you have the following objects
Object | A | B | C | D | E |
---|---|---|---|---|---|
Value | 10 | 8 | 7 | 6 | 4 |
Weight | 8 | 4 | 3 | 3 | 1 |
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 greatest value per weight (E).
Consider the following state space solution. Assume that the objects have names that can be listed alphabetically.
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?
For example, if S = { A,B } then Error(S) = max(12-10,0) + max(20-18,0) = 2+2
= 4.
If S= { A } then Error(S) = max(8-10,0) + max(20-10,0) = 0+10 = 0.
What are the neighbors of the state { A,E }? Which will the hill-climbing algorithm go to? What happens on the next iteration?