algorithm - 两个成对的子集总和

Question

这是一道面试题：

4 个人 - 每人可以在 1、3、7 和 10 分钟内过桥。一次只能两个人走桥。他们过桥需要多少分钟？

我可以手动想到一个解决方案：10 和 7 在一起，一旦 7 到达目的地，“3”跳进去，10 和 3 一起完成。现在 1 自行消失，总时间为 11。因此，{10, 7} 后跟 {10, 3} 后跟 {1}。

我无法考虑如何将其实现为通用算法的代码。有人可以帮我确定如何将这个想法转换为一些真实的代码吗？

Answer 1

您描述的问题不是子集和。

然而你可以：

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

这不是子集和问题，而是作业车间调度问题。请参阅有关作业车间调度的 Wikipedia 条目。你有四个“工作”，分别需要 1、3、7 和 10 分钟，还有两个“车道”来进行它们，即桥梁的容量 2。一般来说，为作业车间调度计算精确的解决方案是很困难的。