## Non-deterministic algorithm for KNAPSACK

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