如何在一个数组中求出任意几个数的和等于给定数?( Python 实现)

2018-01-15 23:20:58 +08:00
 hactf

本来一开始想尝试写个报账的小脚本,后来发现水比较深啊!希望有大佬可以指点迷津。

6841 次点击
所在节点    Python
18 条回复
neosfung
2018-01-15 23:42:27 +08:00
3sum?
holajamc
2018-01-16 00:06:21 +08:00
quinoa42
2018-01-16 02:39:46 +08:00
https://en.wikipedia.org/wiki/Subset_sum_problem
NP-complete 的,只能暴搜了
所以用 @holajamc 的写法可能是比较优美的解决方案了
geelaw
2018-01-16 02:48:29 +08:00
naive 的动态规划对付这个问题应该已经够了吧…
ericls
2018-01-16 02:52:31 +08:00
gnaggnoyil
2018-01-16 08:24:59 +08:00
@geelaw 所谓动态规划做法相比于暴搜真正的优化不外乎是把状态从有序的数列给合并成无序的子集,那既然如此为何不直接对着所有子集枚举呢,就像 2L 所做的那样,还省下了用来记忆状态的空间.
lrxiao
2018-01-16 08:47:38 +08:00
@gnaggnoyil 2^n*N 和 sum*N 一样吗..
wizardoz
2018-01-16 09:33:55 +08:00
这不是动态规划的教材问题吗?
holajamc
2018-01-16 09:41:36 +08:00
我觉得关于动态规划的讨论已经偏离了楼主的需求= =
heww
2018-01-16 10:09:16 +08:00
我去年弄过这个东西,用遗传算法,有想不到的结果。
gnaggnoyil
2018-01-16 11:25:45 +08:00
@lrxiao sum*N 又是哪里来的……
lrxiao
2018-01-16 11:46:12 +08:00
@gnaggnoyil dp 的状态数是 sum * N 啊..所以复杂度也是这个
geelaw
2018-01-16 12:14:43 +08:00
@gnaggnoyil 对于日常情况来说 给定数 常常远小于 2^条目数

@holajamc #9 为什么?
holajamc
2018-01-16 12:29:37 +08:00
@geelaw
我感觉动态规划已经不符合楼主的『小脚本』的需求了,即使暴力穷举也能在短时间内满足其需求
geelaw
2018-01-16 12:37:16 +08:00
@holajamc 是你觉得动态规划太复杂,但其实并非如此
holajamc
2018-01-16 12:41:42 +08:00
@geelaw
我没有讲过动态规划复杂,相反我也在实际的代码中使用
但我仍然没有觉得楼主的需求有**任何**必要使用动态规划
ykk
2018-01-16 13:01:24 +08:00
这个 leetcode 有吧 小脚本建议穷举
maggch
2018-01-16 13:19:21 +08:00
是要求方案数,还是输出所有方案,还是求是否存在。说清楚。不然没人能给你正确答案。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/423163

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX