[讨论讨论,加米加米] Leetcode 881 Boats to Save People 救生艇

求讨论一个贪心算法，对应Leetcode 881,参考 http://www.bubuko.com/infodetail-2738349.html（注：这个帖子时间复杂度应该是O（N logN），末尾分析忘掉了排序） 这里排序过后用两个指针，一个指向"胖子"，一个指向"瘦子", 类似2Sum/3Sum的方法。但是LZ想了很久不知道这个贪心法怎么证明。（注意题目一个boat最多载两个人）LZ想到的贪心法其实是从先选胖子（还没上船人中最胖的一个人），然后选瘦子，从剩下的人中选择能和胖子配对的最重的瘦子，如果没有瘦子可以和胖子配对那就单独分一个船单独装胖子。这个是一个O(N^2)的算法，会超时。

我们用到的方法是双指针贪心算法。

　　如果最重的人可以与最轻的人共用一艘船，那么就这样做。否则，最重的人不能与任何人配对，所以他们得到自己的船。

　　这样做的原因是因为如果最轻的人可以与任何人配对，他们也可以与最重的人配对。让p到目前最轻的人，让p[j]到最重的人。然后，如上所述，如果最重的人可以与最轻的人共享船（如果p[j] +p[i] <=限制），那么这样做;否则，最重的人坐在自己的船上。[/i]

如果没有一个船可以载两个人的限制，很容易找到counterexample:
[2,2,2,3,3] 6

如果没有一个船可以载两个人的限制用双指针得出的答案是3，但是显然答案是2： [2,2,2] [3,3] (所有船装满)

不知道有没有同学知道这个“双指针”贪心法怎么在881的限制中证明呢？讨论有米。

- 你的implementation不够强所以没过. 用二分去找下一个满足的重量就可以了 ibb.co/gt4PCmd
- 再回到你的greedy问题, 为什么用最小的而不用一个更大的重量去满足.
  显然, 最大的重量已经进去了, 且你知道只能再放一个人进去. 你也说了, 想找最大满足条件的重量.
  事实上呢, 你找任何一个<=optimal_weight的人都可以. 用数组表示即
  [t, t, t, ..., t, [optimal weight position] f, f, f, .., f]  t = true, f = false
  注意到optimal_weight是会逐渐递增的. 如果当前你选了optimal weight, 那么当你选下一个, 即更轻一些的大重量时, 对应的optimal weight的位置会升高. 显然是sub problem, 所以greedy解法满足.
  其实大多数情况下greedy只是dp的一个特殊情况, 此题恰满足而已.
- 如果没有限制, 希望多放重量少用船的, 显然是个set covering problem
  一般题目是给定船数算limit, 见875

这道题比不是背包问题，传统的背包问题是策略型问题，求的是最优得利方案，比如每个人重量不等，付的船票费不等，怎么在船不沉的情况下选那些乘客赚最多的钱，而没被选到的人要自己游泳泅渡。

这题要把瘦子胖子所有人都带上。楼主自己想的哪个把每个船尽量装满的算法，其实也可以是O(nLogN)，数组排序后，从右依序锁定胖子，再二分查找可以容的下的最重的瘦子，不是1/2的N * logN吗？不过楼主问什么任务这个算法不需要证明，而哪个最胖和最瘦坐一起的算法需要证明？

补充内容 (2019-3-28 02:59):
嗯，回帖到一半，走开回来提交的，没看见337845818的回复。其实，这题选了当前最重的胖子以后，任选一个选最重的瘦子是等价的。这个面试时可列举说明，无需严谨的数学证明。选最瘦的瘦子是方便双指针操作并不是故意

如果没有的两个人的限制，这个问题是不是就类似于背包问题了呢，对每一个新的包/船，都尽量装满。 不太明白还能怎么用贪心来做这个问题。。