74 lines
2.4 KiB
Plaintext
74 lines
2.4 KiB
Plaintext
include xpllib; \for Print and IntSize
|
|
def N = 22; \number of Items
|
|
int Items, S(N);
|
|
def \Items\ Name, Weight, Value, Count;
|
|
|
|
proc Knapsack(W);
|
|
int W;
|
|
int I, J, K, V, MM, M;
|
|
[MM:= Reserve((N+1)*(W+1)*IntSize);
|
|
M:= Reserve((N+1)*IntSize);
|
|
M(0):= MM;
|
|
for I:= 1 to N do
|
|
[M(I):= @MM(I*(W+1));
|
|
for J:= 0 to W do
|
|
[M(I, J):= M(I-1, J);
|
|
for K:= 1 to Items(I-1, Count) do
|
|
[if K*Items(I-1, Weight) <= J then
|
|
[V:= M(I-1, J-K*Items(I-1, Weight)) + K*Items(I-1, Value);
|
|
if V > M(I, J) then M(I, J):= V;
|
|
];
|
|
];
|
|
];
|
|
];
|
|
I:= N; J:= W;
|
|
while I > 0 do
|
|
[V:= M(I, J);
|
|
K:= 0;
|
|
while V # M(I-1, J) + K*Items(I-1, Value) do
|
|
[S(I-1):= S(I-1) + 1;
|
|
J:= J - Items(I-1, Weight);
|
|
K:= K+1;
|
|
];
|
|
I:= I-1;
|
|
];
|
|
];
|
|
|
|
int I, TC, TW, TV;
|
|
[Items:= [
|
|
["map ", 9, 150, 1],
|
|
["compass ", 13, 35, 1],
|
|
["water ", 153, 200, 2],
|
|
["sandwich ", 50, 60, 2],
|
|
["glucose ", 15, 60, 2],
|
|
["tin ", 68, 45, 3],
|
|
["banana ", 27, 60, 3],
|
|
["apple ", 39, 40, 3],
|
|
["cheese ", 23, 30, 1],
|
|
["beer ", 52, 10, 3],
|
|
["suntan cream ", 11, 70, 1],
|
|
["camera ", 32, 30, 1],
|
|
["T-shirt ", 24, 15, 2],
|
|
["trousers ", 48, 10, 2],
|
|
["umbrella ", 73, 40, 1],
|
|
["waterproof trousers ", 42, 70, 1],
|
|
["waterproof overclothes", 43, 75, 1],
|
|
["note-case ", 22, 80, 1],
|
|
["sunglasses ", 7, 20, 1],
|
|
["towel ", 18, 12, 2],
|
|
["socks ", 4, 50, 1],
|
|
["book ", 30, 10, 2] ];
|
|
TC:= 0; TW:= 0; TV:= 0;
|
|
Knapsack(400); \maximum weight = 400 decigrams = 4.0 killograms
|
|
for I:= 0 to N-1 do
|
|
[if S(I) then
|
|
[Print("%s %5d %5d %5d\n",
|
|
Items(I, Name), S(I), S(I)*Items(I, Weight), S(I)*Items(I, Value));
|
|
TC:= TC + S(I); \accumulate totals
|
|
TW:= TW + S(I)*Items(I, Weight);
|
|
TV:= TV + S(I)*Items(I, Value);
|
|
];
|
|
];
|
|
Print("%s %5d %5d %5d\n", "count, weight, value: ", TC, TW, TV);
|
|
]
|