subset sum in pairs of two

Question

This is an interview question:

4 men- each can cross a bridge in 1,3, 7, and 10 min. Only 2 people can walk the bridge at a time. How many minutes would they take to cross the bridge?

I can manually think of a solution as: 10 and 7 got together, as soon as 7 reaches the destination, '3' hops in and 10 and 3 complete together. Now 1 goes by itself, and total time taken is 11. So, {10, 7} followed by {10, 3} followed by {1}.

I am unable to think about how I can implement this into a general algorithm into a code. Can someone help me identify how I can go about converting this idea into some real code?

Answer 1

The problem you describe is not subset sum.

Yet you can:

order the array a by descending time
int time1 = 0;  // total time taken by the first lane
int time2 = 0;  // total time taken by the second lane
for i : 0..n
    if(time1 < time2)   // add the time to the most "available" lane
        time1 += a[i];
    else
        time2 += a[i];
    endif
endfor
return max(time1, time2);

Answer 2

This is not a subset sum problem but a job shop scheduling problem. See Wikipedia entry on Job shop scheduling. You have four "jobs", taking 1, 3, 7 and 10 minutes respectively, and two "lanes" for conducting them, that is, the capacity 2 of the bridge. Calculating exact solution in general for job shop scheduling is hard.