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

a49481 发表于 2022-3-30 22:07
这是一个np问题，简单的证明如下：
（1）可以简单的理解为原问题是：限制子数组的和，求二维数组的长度最 ...

原先的证明思路太绕，而且不严谨，但是可以很确定地说这个就是一个NP问题，证明NP的更好的思路是这样：
（1）首先，可以简单的理解为原问题是：限制子数组的和不超过Limit，求二维数组的长度Length最小值L_min。我们假设我们有一个算法A，可以在T时间内得到这个问题的解；
（2）现在，记原数组内所有数的和为s，然后令Limit = s / 2，求二维数组的长度Length最小值L_min。我们发现，一旦知道了L_min的值，通过比较L_min和2的大小关系，我们就可以得到以原数组为input的Partition Problem的解（如果L_min > 2，Partition Problem的答案就是no，否则就是yes）。因此，在知道原问题的算法A的运行结果情况下，我们可以在常数时间内得到Partition Problem的答案，也就是说通过算法A，Partition Problem也能在T时间内得到答案。
（3）因此，原问题至少和Partition Problem有一样计算复杂度。由于Partition Problem是NP问题，因此原问题是NP问题。


关于什么是Partition Problem，可以看这里：https://en.wikipedia.org/wiki/Partition_problem

sybzd 发表于 2022-03-30 21:38:11
20

greedy出来是

换个思路，还是取最大数，剩下递归，找最长数列，然后剩下的继续？

https://en.wikipedia.org/wiki/Bin_packing_problem
看起来是裸题

a49481 发表于 2022-3-31 01:14
原先的证明思路太绕，而且不严谨，但是可以很确定地说这个就是一个NP问题，证明NP的更好的思路是这样：
...

是Bin packing problem，没理解错的话应该是一摸一样

lu9999 发表于 2022-03-31 00:14:26
换个思路，还是取最大数，剩下递归，找最长数列，然后剩下的继续？

肯定也不对
第一，如何找最长序列？
第二，最长序列肯定是从小数开始。如果把小数都用了，后面的大数就不好配对了

a87009751 发表于 2022-3-31 00:18
leetcode 881变种

881可以greedy，因为881最多两个人一艘船，这里则没有限定。

这道题不能用greedy来算，我来个反例：list = [2,2,2,2,3,3], limit = 7。greedy的结果是[2],[2,2,2],[3,3]，但结果应该是[2,2,3],[2,2,3]。记得leetcode上有个类似的周赛题，印象中最后就是暴力算的。
不过考虑到这是公司面试题，盲猜是考官没想明白打算让你greedy的

yangff 发表于 2022-03-31 03:15:52
是Bin packing problem，没理解错的话应该是一摸一样

很棒，直觉告诉我这一定是一个有名字的问题，但是我找不到，只能想办法证明。非常感谢科普！

感觉是直球BinPacking， Greedy应该只能用来估算的（这个问题还有一堆估计算法）。

NP completeness and Hardness proof： https://cs.ubishops.ca/home/cs567/more-np-complete/rangasamy-bin-packing.pdf

乱写的DP解：

1. 
   
2. from typing import List
   
3. class Solution:
   
4.     def minimumBinPacking(self, nums: List[int], capacity: int):
   
5.         # if the sum of a subset is less than capacity
   
6.         def valid_subset(mask):
   
7.             acc = 0
   
8.             for i, x in enumerate(nums):
   
9.                 if (mask>>i)&1 == 0:
   
10.                     continue
    
11.                 acc += x
    
12.                 if acc > capacity:
    
13.                     return False
    
14.             return True
    
15.         
    
16.         n = len(nums)     
    
17.         valid_subsets = {state for state in range(1<<n) if valid_subset(state)}
    
18.         dp = [float('inf') for _ in range(1<<n)]
    
19.         dp[0] = 0
    
20.         
    
21.         # iterate through all states
    
22.         for state in range(1, 1<<n):
    
23.             subset = state
    
24.             # iterate through all subsets
    
25.             while subset > 0:
    
26.                 if subset in valid_subsets:
    
27.                     dp[state] = min(dp[state], 1 + dp[state-subset])
    
28.                 subset = (subset-1)&state
    
29.         return dp[-1]
    
30. 
    
31. 
    
32. if __name__ == "__main__":
    
33.     s = Solution()
    
34.     assert s.minimumBinPacking([1, 2, 2, 3, 4, 5, 6], 6)==4, "first test case failed"
    
35.     assert s.minimumBinPacking([2, 2, 2, 3, 3, 5], 6)==3, "second test case failed"
    
36.     assert s.minimumBinPacking([2,4,4,6,7,7,10], 20) == 2, "third test case failed"
    

复制代码

HOI3CHI 发表于 2022-03-31 10:40:47
881可以greedy，因为881最多两个人一艘船，这里则没有限定。

用一个stack就能greedy了。stack里的元素是船，数组从大到小往船上加，船装满了==limit就pop出去，没装满＜limit但装不下next person就留在stack里，往里push下一条船。最后看一共create了几条船

补充内容 (2022-04-02 04:18 +08:00):
错了，不是stack，是min pq