Introduction to Artificial Intelligence: Programming assignment 1

Assigned: Jan. 17
Due: Feb. 7

Implement a program that solves the KNAPSACK problem using iterative deepening over the search space described in problem 1, problem set 1.

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:

A 70 80
B 50 50
C 50 50

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


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


You may write your program in Pascal, C, or Java. If you want to use any other language, you must get the approval of the grader. 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.


You should email to the grader:


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