贪心算法-背包相关问题3
背包相关问题3-乘船问题
有n个人，第i个人重量为Wi，每艘船最多只能载两个人，最大载重为C,求最少需要几只船?
这个问题可以算做稍难的背包问题了,粗看，并没有一个很好的办法，想把这些人按重量排序，但排序又什么用呢，其实，我们再细想想，就会有头绪了，要想船最少，肯定希望有更多的船能载两个人，这时候，最轻的那个人就发挥作用了，我们假设这个人重量为x,那个当重量大于C-x的人一定只能坐一条船了，所以，思路就出来了，我们只需要找到能和最轻的人配对的最重那个人就行，然后依次找次轻的人，再找能和它配对的最重的，依次查找，结果就出来了。代码如下: