Assigned: Jan. 17

Due: Jan. 24

The KNAPSACK problem is defined as follows: You are given a collection
of *N* objects.
Each object has a specified weight and a specified value.
You are given a capacity, which is the maximum total weight you can
carry, and a quota, which is the minimum total value that you want to get.
The problem is to find a subset of the objects whose total weight is
at most equal to the capacity and whose total value is at least equal
to the quota.

For example, suppose that you are given three objects:

Object Weight Value A 70 80 B 50 50 C 50 50and you are given a capacity of 110 and a quota of 90. Then a solution to the problem is the set { B,C }. Note that there is no solution involving object A, because once you have put A in the knapsack, there is no room for the other two. (You are not allowed to choose a fraction of an object.)

It is believed that there is no efficient algorithm that always finds a solution to KNAPSACK when one exists. (In the technical jargon, the problem is NP-complete.)

This problem can be formulated as state-space search as follows:
Arrange the objects in some order O.
A * state * is any set of objects whose total weight is not more than
than the capacity. An * operator * on state S is to find
an object X in S such that Weight(S) + Weight(X) <= Capacity
and such that the name of X is later in order O than any of the objects in
S, and add X to S. A * goal state * is one whose value is
greater than or equal to the quota. The * start state * is the
empty set.

A. Is this state space a tree? Explain your answer.

B. What is the maximum branching factor, as a function of *N*, the
number of objects?

C. Give an upper bound on the distance from the start state to the
goal state, as a function of *N*.

D. Give an upper bound on the maximum size (number of states) in the
state space, as a function of *N*.

E. Consider the following collection of objects:

Name: A B C D E F G H I Weight: 70 60 50 40 30 20 10 10 1 Value: 260 245 200 100 80 65 60 60 10with a capacity of 100 and a quota of 400.

Assume that different branches of the search spaces are explored in alphabetical order. What is the first solution that is found in a depth-first search?

A. Characterize this search method formally, after the style of problem 1. (That is, what is a state? What is an operator? What is the goal? What is the start state.)

B. Using the same collection of objects as in Problem 1, part E, and assuming, again, that different branches are explored in alphabetical order, what is the first solution that is found in a depth-first search?