Artificial Intelligence: Programming Assignment 1

Assigned: Jan. 23
Due: Feb. 13

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

The KNAPSACK problem can be solved using the following non-deterministic algorithm:

KNAPSACK (in OS : set of objects; QUOTA : number; CAPACITY : number;
          out S : set of objects; FOUND : boolean)
begin S := empty;
      total_value := 0;
      total_weight := 0;
      FOUND := false;
      pick an order L over the objects;
      loop 
         choose an object O in L;
         add O to S;
         total_value := total_value + O.value;
         total_weight := total_weight + O.weight;
         if total\_weight > CAPACITY then fail
           else if total\_value > = QUOTA 
                  FOUND := true;
                  succeed;
          endif endif
         delete all objects up to O from L;
       endloop
end

Implement a program that solves the above algorithm for KNAPSACK using iterative deepening.

Input format

The program should take its input from standard input. The input file will contain a number of problems in sequence. Each problem has the following format.

First line. "***"
Second line. Capacity.
Third line. Quota.
Fourth line. Number of objects
Remaining lines: 1 line per object. Name, weight, and value, separated by blanks.

There can be any number of blank lines separating problems.

You may assume that:
There are at most 20 objects.
A name is a single alphabetical character.
All quotas, capacities, weights, and values are integers.

For example, an input file containing the two examples in the problem set would have the following form:

***
110
90
3
A 70 80
B 50 50
C 50 50

***
100
400
9
A 70 260
B 60 245
C 50 200
D 40 100
E 30 80
F 20 65 
G 10 60
H 10 60
I  1 10

Output

The program should give its output in standard output. It should have the following form:
"Solution:" Set of objects in solution. 
"Total weight:" Total weight
"Total value:" Total value
"Number of nodes in last pass:" Number of nodes generated in final iteration of the outside loop of the iterative deepening
"CPU time:" Total CPU time required.
If no solution exists, then the output for the program should be just "No solution".

For example, the output for the first problem above might be

Solution: {B,C} 
Total weight: 100
Total value: 100
Number of nodes in last pass: 3
CPU time: 1 msec.

Test file:

A test file with 20 sample problems will be made available here. .

Program:

You may use any language that I can run on the Sun network. The program should be well-structured and commented.

The program must use iterative deepening. No more than half credit will be given for a program that uses any other method of solution.

Deliverable

You should email to me:

Grading

Running correctly: 75%.
Well-written code: 20%
Well commented: 5%