Many years ago, I published an APL algorithm (see, McLeod, 1983, below) for the cargo loading problem. The cpu timings I have performed over the years show the amazing improvements in speed as well perhaps as quality of software. The Cyber computer listed was a state of the art mult-million dollar machine which required a huge staff. The VAX system was also very expensive, around $500,000 and required a lot of maintenance. I believe that the quality of the APL implementation on these machines was also inferior to that of APL*PLUS II. That's another story. When software became separated from the computer vendor in the PC revolution, quality improved greatly.
Suppose that there are 8 items and that an unlimited quantity
of each item is available. If the profit per item is
72 60 40 27 20 50 85 96
and the weight per item is
20 18 14 12 10 16 22 24
Then form the following matrix, A
72 60 40 27 20 50 85 96
20 18 14 12 10 16 22 24
99 99 99 99 99 99 99 99
Then the maximum profit and the number of items to select may be
obtained from the APL
function CARGO published in McLeod (1983).
81 CARGO A
This yields the following output
297 0 0 0 0 1 0 1 2
which means maximum profit = 297, with x = (0,0,0,0,1,0,1,2).
Machine and APL Version | CPU Time in Seconds |
Cyber 825/NOS, CDC APL | 17.8 |
VAX 785/11 VMS, VAX APL | 142.9 |
PC 286/7 10 MHZ, APL*PLUS II | 72.6 |
PS/2 386/7 25 MHZ APL*PLUS II | 15.9 |
PS/2 486 DX-50, APL*PLUS II | |
IBM Thinkpad, Pentium-120 | 2.0 |
An APL workspace dump is available here.
McLeod, A.I. (1983). ``The cargo-loading or knapsack problem by dynamic programming'', APL Quote Quad, 14, pp.21-22.