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.

**Answer:** Yes. Because of the restriction that objects are added
to set S in the order they are given in O, there is only one way of
creating a given set S, and therefore only one path to the state S.

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

** Answer: ** At the root, the branching factor is *N*. At all
other states, the branching factor is less than *N*. Hence, the
maximum branching factor for the space is *N*

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

**Answer:**
There can be at most *N* operations from the start state to any
other state, as each operation adds another element to *S*.

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

** Answer: **
A crude answer would be [Branching factor] ** [Depth]; i.e. N^{N}.
A better estimate would be to observe that there are 2^{N} different
subsets of N objects, and hence at most 2^{N} different states. This
bound can actually be acheived, if the only solution involves putting all
the objects in the knapsack.

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?

** Answer: ** {B,F,G,H}

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

** Answer:**A state is a set of objects whose total value is at least
the quota. The operator is to remove an object that comes later in order
O than any object previously removed. The goal is a state whose total
weight is at most the capacity. The start state is the set of all objects.

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?

** Answer: **
{C,E,G,H}