## 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.

• 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. The total 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.

### 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).
• Is the state space a tree?
• Give an upper bound on the depth of the state space.
• What is the branching factor?
• Is the depth of the shallowest goal known in advance?

### Problem 3

An alternative approach is to use a hill climbing algorithm. Consider the following state space with heuristic function:
• A state is any set of objects.
• An operator is either to delete an object in the set or to add an object into the set.
• For any set S, let Weight(S) and Value(S) be the total weight and total value of the set. Define the error function Error(S) = max(Weight(S)-M,0) + max(T-Value(S),0).
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?