Problem Set 3

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.

Problem 1

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?

Problem 2

Consider now the general problem in which you have N objects. Characterize the state space for the general problem (NOT for the specific example).

Problem 3

An alternative approach is to use a hill climbing algorithm. Consider the following state space with heuristic function: Then the problem is to find a set S for which Error(S)=0.

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?