求问一道面经算法题，不知道用哪种方法

今天正好刷到原题。1986
果真是数据规模很小只有14，是二的n次方

a87009751 发表于 2022-4-1 16:10
用一个stack就能greedy了。stack里的元素是船，数组从大到小往船上加，船装满了==limit就pop出去，没装满 ...

还是不太懂 lc原题上大家都backtracking的。

a87009751 发表于 2022-4-1 15:10
用一个stack就能greedy了。stack里的元素是船，数组从大到小往船上加，船装满了==limit就pop出去，没装满 ...

1. 
   
2. if __name__ == "__main__":
   
3.     '''
   
4.     其实就是binpacking里用来估算的best fit first decreasing
   
5.     '''
   
6.     def 迫真贪心881(nums, capacity):
   
7.         list.sort(nums)
   
8.         start, end, res = 0, len(nums)-1, 0
   
9.         ship_room = capacity
   
10.         while start <= end:
    
11.             print(start, end, res)
    
12.             if nums[start] + nums[end] <= ship_room:
    
13.                 ship_room -= nums[start] + nums[end]
    
14.                 start += 1
    
15.                 end -= 1
    
16.             elif nums[end] <= ship_room:
    
17.                 ship_room -= nums[end]
    
18.                 end -= 1
    
19.             elif nums[start] <= ship_room:
    
20.                 ship_room -= nums[start]
    
21.                 start += 1
    
22.             else:
    
23.                 res += 1
    
24.                 ship_room = capacity
    
25.         if ship_room == capacity:
    
26.             return res
    
27.         return res + 1
    
28.    
    
29.     xs = [1,2,2,2,3,3,2,3,2]
    
30.     a = 10
    
31.     assert 迫真贪心881(xs, a)==2, "照搬881的greedy做法，被分成了[[1,3,2,3],[2,3,2,2],[2]]， 而不是[[1,3,3,3],[2,2,2,2,2]]。如果一个数要被分成很多部分才能完美凑出来，直接sort肯定是可能错过最优解的。"
    

复制代码

没弄错的话应该是你说那个881的思路，并不保证最优解。

SoWhat0309 发表于 2022-4-1 18:18
没弄错的话应该是你说那个881的思路，并不保证最优解。

我补充了，要用min pq。

1. class Solution {
   
2.     public int numRescueBoats(int[] people, int limit) {
   
3.         Arrays.sort(people);
   
4.         PriorityQueue<Integer> pq = new PriorityQueue<>();
   
5.         int i = people.length - 1;
   
6.         int count = 0;
   
7.         while(i >= 0){
   
8.             if(pq.isEmpty()){
   
9.                 pq.add(people);
   
10.                 i--;
    
11.             }
    
12.             else{
    
13.                 int last = pq.peek();
    
14.                 if(last + people < limit){
    
15.                     pq.poll();
    
16.                     pq.add(last + people);
    
17.                 }
    
18.                 else if(last + people == limit){
    
19.                     pq.poll();
    
20.                     count++;
    
21.                 }
    
22.                 else{
    
23.                     pq.add(people);
    
24.                 }
    
25.                 i--;
    
26.             }
    
27.         }
    
28.         count += pq.size();
    
29.         return count;
    
30.     }
    
31. }

复制代码

a87009751 发表于 2022-4-2 12:52
我补充了，要用min pq。

用PriorityQueue找剩余空间最大的船看上去像那么回事，但你一个数多拆几次一样也不行了啊，能过[1,2,2,2,2,2,3,3,3], 10的case， 到[2,3,3,4,4,4,5,6,7,10]，12又不行了。NP完全的题要求精确解而不是估算的话，就是没法套881那种题去贪心的啊。

二分猜最小的size

SoWhat0309 发表于 2022-4-2 13:20
用PriorityQueue找剩余空间最大的船看上去像那么回事，但你一个数多拆几次一样也不行了啊，能过[1,2,2,2, ...

研究了你的case，唯一的解[2, 10], [3,3,6], [4,4,4], [5,7]。贪心确实不行，任何一个数字位置不对就解不出来，我把问题想简单了，谢谢指正。