Three Boys And A Canoe
March 15, 2016
In the previous exercise we looked at a simple programming problem: determining the number of canoes needed for a group of boy scouts of varying weights, where each canoe could hold two boys. Today we extend that problem to the case of three boys or, more generally, n boys.
Your task is to modify your previous solution to handle the case of three boys; if you are ambitious, handle the case of n boys. There is no suggested solution, as I am on vacation visiting my daughter in Houston and don’t have time to write one. Feel free to post your solutions or discuss the exercise in the comments below.
Programming Praxis 
function create_weights_vector(n::Int64, mw::Int64 = 150)
w = round(Int64, 10*randn(n) + 75)
w[w .> mw] = mw
return w
end
function find_number_of_kayaks(w_::Array{Int64, 1}, k::Int64 = 3, mw::Int64 = 0)
if mw == 0
mw = 75*k
end
mw1 = mw + 1
w = copy(w_)
n = length(w)
z = Array(Int64, n)
c = 1
combos = collect(combinations(1:n, k))
N = length(combos)
d = Array(Int64, N) # distances vector for all possible combos
for i = 1:N
d[i] = mw – sum(w[combos[i]])
end
d[d .< 0] = mw1 # make negative differences really unattractive solutions
while true
ind = indmin(d) # index of best combo
if d[ind] < mw
q = combos[ind]
z[q] = c
w[q] = mw1
for i = 1:N
for j = 1:k
if q[j] in combos[i]
d[i] = mw1
break
end
end
end
c += 1
else # check if a single kid can go aboard (all usable combos have been exhausted)
for i = 1:n
if w[i] <= mw
w[i] = mw1
z[i] = c
c += 1
end
end
return z, maximum(z)
end
end
end
This solution works for various values of boat sizes (including 2 and 3) and is fairly fast. Adjusted the maximum weight that each vessel can hold, so that it ensures a capacity of n, for the majority of cases. Solution for 100 passengers and canoes having capacity of 3 takes about 0.58 sec on my laptop (without using multi-threading).
Nice optimization problem. Here’s a backtracking solution in Haskell:
An allocation for some list of weights is an allocation to a single canoe of the largest weight and some other weights (such that we can’t add any more to the canoe without exceeding the limits) and an allocation of the remaining weights.
For the parameters above, we find 70 solutions using 4 or 5 canoes, the first few are:
And here is a backtracking solution in C++ using essentially the same method as the previous Haskell solution. We use Knuth’s dancing links trick to swap elements in and out of a double linked list (so the root always points to the list of unallocated elements). To keep things simple, this one doesn’t impose a limit on the number of boys per canoe, just the total weight (and the output format is a rather minimalistic).
#include <stdio.h> #include <stdlib.h> struct Node { Node(Node *prev_, Node *next_, int value_) : prev(prev_), next(next_), aux(0), value(value_) {} Node *prev; Node *next; Node *aux; int value; }; void remove(Node *p) { p->prev->next = p->next; p->next->prev = p->prev; } void restore(Node *p) { p->prev->next = p; p->next->prev = p; } void show(Node *p, bool top) { if (p) { show(p->aux,false); printf("%d%s", p->value, top?"\n":" "); } } Node *root; int total; // t is allocation so far, s is remaining elements void scan1(Node *t, Node *s); // sum is total weight for current canoe. void scan(Node *t, Node *s, int sum) { for ( ; s != root; s = s->next) { int a = s->value; if (sum+a <= total) { remove(s); s->aux = t; scan (s, s->next, sum+a); // recurse with s in the set restore(s); } } if (root->next == root) { show(t,true); // All elements used, we have a solution. } else { int min = root->prev->value; // last element is smallest if (sum + min > total) { // check set is maximal scan1(t,root->next); } } } void scan1(Node *t, Node *s) { if (s->value <= total) { s->aux = t; remove(s); scan(s, s->next, s->value); restore(s); } } int main(int argc, char *argv[]) { int count = atoi(argv[1]); total = atoi(argv[2]); root = new Node(0,0,0); root->prev = root->next = root; for (int i = 1; i <= count; i++) { Node *p = new Node(root,root->next,i); restore(p); // Insert in list at front. } scan1(0,root->next); }Sample output: