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

greedy的话如果输入是[2,3,4,5,6],limit=10的话会得到[[2,6],[3,5],[4]]吧？实际上应该是[[2,3,5],[4,6]]，不知道理解的对不对

mushicyf 发表于 2022-3-31 11:12
greedy的话如果输入是[2,3,4,5,6],limit=10的话会得到[[2,6],[3,5],[4]]吧？实际上应该是[[2,3,5],[4,6]]， ...

好像greed有点问题，哈哈

mushicyf 发表于 2022-03-30 20:12:58
greedy的话如果输入是,limit=10的话会得到,,]吧？实际上应该是,]，不知道理解的对不对

greedy吧，从最大的开始，一直从最大的开始加，直到找到是target或者找不到就拿出来，再继续
先取6，然后从5往前，5不行，取4，刚好10，拿出来，剩下里面继续，拿5，3还能拿再拿2，结束
因为是排序的，取了元素后只可能再拿比自己小的
复杂度o2次方

leetcode 881变种

lu9999 发表于 2022-3-30 21:10
greedy吧，从最大的开始，一直从最大的开始加，直到找到是target或者找不到就拿出来，再继续
先取6，然后 ...

[2，4，4，6，7，7，10] 20

greedy出来是[10,7,2] [7,6,4] [4]
实际上是[10,6,4] [7,7,4,2]

楼主问了数据规模没有？
这道题看起来像是2的n次方
我只能想到很笨的解法。而且和sort不sort没关系。
用dp存数组的任意状态，用二进制表示数组那些element 被拿走了，那些还在，比如11111111就是初始状态，
状态转移就是取任意个还没被取走的数，他们和小于limit作为一个result里面的element
[1, 2, 3] , 3
start : 111
f(111) = min(1 + f(110), 1 + f(101), 1 + f(001), 1 + f(011))
对应的就是
1. 取出3
2. 跳过 3 取出2
3. 跳过 3 取出2 取出1
4, 跳过 3 跳过 2 取出1

dp的size是2的n次方，状态转移也是2的n次方（数组中未被取走的数所有combination）

这是一个np问题，简单的证明如下：
（1）可以简单的理解为原问题是：限制子数组的和，求二维数组的长度最小值（当然这里要求同时给出一个构造解，但是为了简化讨论，认为就是求二维数组的长度最小值，不影响结论);
（2）现在考虑原问题的对偶问题：限制二维数组的长度，考察和最大的那个子数组，求这个最大子数组和的最小值
（3）现在考虑对偶问题的一个特殊情况，限制二维数组的长度不能超过2，求最大子数组和的最小值。注意到，这是一个经典的np-hard问题，这个问题实际上就是Partition Problem的变体：https://en.wikipedia.org/wiki/Partition_problem

现在来总结：如果（2）中的对偶问题有polynomial的解，那么（3）中的np-hard问题就也有一个polynomial的解，因为（3）只是（2）的一种特殊情况。因此，（2）中的对偶问题比（3）中的np-hard问题要困难，于是（2）中的对偶问题也至少是np-hard。因为对偶问题是np，所以原问题也是np。

因此，这个问题不存在greedy的解法，要么状压dp，得到一个pseudo polynomial的答案，要么就是遍历做backtracking去搜得一个符合要求的最优解。考虑到这个，我觉得楼上这位同学的思路应该有可能是对的，当然我还没有认真看。

贪心不对 只有状压DP可以 2^N

补充内容 (2022-03-31 14:04 +08:00):
雀氏是3^N 需要枚举子集的子集

楼上关于状态压缩动态规划的时间复杂度好像算的不太对。

设 |S| 为 S 二进制表示下 '1' 的个数，那么根据二项式定理可求解时间复杂度为O(3^n)

sybzd 发表于 2022-3-30 22:07
楼主问了数据规模没有？
这道题看起来像是2的n次方
我只能想到很笨的解法。而且和sort不sort没关系。

不出意外的话，这就是最优解