program processorEfficientHypercubeAlgorithmsForTheKnapsackProblem; (*{{{ documentation*) (* Taken from the work Processor Efficient Hypercube Algorithms for the Knapsack Problem by Jianhua Lin and James A. Storer. published in the Journal of Parallel and Distributed Computing 11, 332-337 (1991). Department of Computer Science, Brandeis University, Waltham, Massachusetts 02254. *) (*}}} *) (*{{{ const, types and variables*) const max = 8; type vector = array [0..max] of integer; matrix = array [0..max] of vector; var n : integer; (* number of processors *) m : integer; (* number of objects *) c : integer; (* capacity *) w : vector; (* weights *) p : vector; (* profits *) d : integer; (* number of components of F[j][c] assigned to each processor *) f : matrix; (*}}} *) procedure readData; (*{{{ readData*) var i : integer; begin write('Number of objects '); read(m); write('Capacity '); read(c); i := 1; while i <= m do begin write('weight profit of object ',i,': '); read(w[i]); read(p[i]); i := i+1; end; write('Number of processors (not greater than capacity) : '); read(n) end (* readData *); (*}}} *) procedure writeData; (*{{{ writeData*) var i, j : integer; begin i := 0; while i < n do begin j := 0; while j < d do begin write('f[',i,'][',j,'] = ',f[i][j],' '); j := j+1 end; writeln; i := i+1 end; write('Press any key to continue ... '); readln; end (* writeData *); (*}}} *) (*{{{ main body*) begin readData; (*{{{ d := [(c+1) /n]*) d := (c+1) div n; if ((c+1) mod n) <> 0 then d := d+1; writeln('d = ',d); (*}}} *) parallel 0..n-1 do (*{{{ f[name][i] := 0 for i = 0,1,...,d-1*) var i : integer; begin i := 0; while (i <= d-1) do begin f[name][i] := 0; i := i+1 end; end (* parallel *); (*}}} *) var j : integer; begin j := 1; while j <= m do var i, first : integer; begin i := 0; while i <= d-1 do begin first := (w[j]-i) div d; if ((w[j] - i) mod d) > 0 then first := first+1; writeln('j = ',j,' i = ',i,' first = ',first); writeData; parallel first..n-1 do (*{{{ f:=max{f[name][i],f[name*d+i-w[j]/d][name*d+i-w[j]\d]+p[j]*) var s,t,r : integer; begin t := name*d+i-w[j]; s := t div d; t := t mod d; r := f[s][t]+p[j]; if f[name][i] < r then f[name][i] := r end; (*}}} *) i := i+1; end (* while i *) ; j := j+1; end (* while j *); end; writeData; end. (*}}} *)