这是一个创建于 1254 天前的主题，其中的信息可能已经有所发展或是发生改变。
https://leetcode-cn.com/problems/partition-equal-subset-sum/
先贴原题:
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
如果现在元素可以弃置,也就是不放入任何一个子集中,求弃置最少元素的分割成 2 个等元素和子集的方案.
如[1,1,3]
即分割成[1][1],3 弃置
目前就想到暴力算法复杂度 3 的 n 次方 ,求个优化思路或者更优方案, 去重 /回溯的剪枝目前也没好的办法
第 1 条附言 · 2020-11-16 17:03:01 +08:00
 |
1
guchengyehai1 2020-11-16 15:02:15 +08:00 via Android
来个 bfs 的，https://codeshare.io/21mWDj
|
|
2
guchengyehai1 2020-11-16 15:18:06 +08:00 via Android
不过从 dp 的角度看，有每个元素三种选择，给第一个子集，给第二个子集，扔掉
|
|
3
guchengyehai1 2020-11-16 15:34:09 +08:00 via Android
https://codeshare.io/2EOYpp 代码没有验证，基本思路应该是这样，再加个 memoization
|
 |
4
geelaw 2020-11-16 15:43:04 +08:00 via iPhone
提示：令 F(a,b) 为前 a 个元素分成两个和的差的绝对值为 b 的子集最少需要删除元素个数。
时间 n*mn，m 是一个元素的最大值，n 是元素个数。对 a 可用滚动数组技巧优化。 |
 |
5
tamer OP @guchengyehai1 时间复杂度是不是没法优化了,目前 n 接近 20 就算不动了
|
|
6
tamer OP @guchengyehai1 有没有办法在过程中剪枝, 因为 存在镜像情况, a b 内的元素 对调
|
|
7
tamer OP |
|
8
guchengyehai1 2020-11-16 17:35:34 +08:00 via Android
改了一版，不知道是不是正确的
|
|
9
guchengyehai1 2020-11-16 18:42:45 +08:00 via Android
验证了一下，memo 优化一下 n 大于 30 都可以跑
|
Select Language