Introduction to Artificial Intelligence: Problem Set 1

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

Problem 1

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   10
with 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?

Problem 2

In problem 1, we explored the space by starting with an empty knapsack and adding one object at a time, as long the total weight was at most the capacity. An alternative method of solving the problem is to start with all the objects in the knapsack, and gradually remove objects, as long as the total value of the objects in the knapsack is at least as great as the quota.

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?