Programming assignment 2000
0/1 Knapsack problem
Write a program to solve 0/1 knapsack problem. As this is a problem
that has no known deterministic algorithm that can solve it in a reasonable
time, you should use heuristic, such as branch and bound method.
To show the bound on running time, please run the experiments, varying
the size of the problem and plot
the number of solutions explored before finding the answer.
The specification of instances of problem is as follows :
N the number of object 1..100 20 is consider
a small size, 100 is a large size (remember that the search space is 2^N)
W the maximum weight 10.. 500,000 (integer)
each object has w 1..1000, v 1..1000 (integer)
The format of your input file is : N W w0 v0 w1 v1 .
. . wn-1 vn-1
It is an ASCII text file with no line break.
The example
A small size problem N=20 (text file) knapsack.inp
This problem has one unique solution. The solution is
max value = 7467
the solution composed of : x3 x4 x5 x6 x7 x8 x9 x11 x15
x16 x18 (numbering started at 0 )
The due date is 25 August 2000 9-12am at Lab1
floor 18 Engineering building 4
What you have to hand-in
1) Run your program (executable). The instructor will supply
you with two input files : one for small size problem (named "small.txt")
the other for large size problem ("large.txt").
2) You have to explain briefly how your program work and answer
some questions. This is to access your understanding.
3) You must submit a report on spot. The report should
contains : a) The explanation how your program work (not necessary
the full listing of the program) preferable in pseudo code.
b) the analysis of the running time of your algorithm and the plot of the
experiments. The report needs not to be long, a brief,
3-5 pages is expected.
Each student will have only 5 minutes to submit his/her work (including
all three above).