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

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.

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

"Solution:" Set of objects in solution.If no solution exists, then the output for the program should be just "No 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.

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.

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

- The source code for the program. Be sure to include your name as a comment at the top of the code.
- The output of the program on the test file.

Well-written code: 20%

Well commented: 5%