如何在一个数组中求出任意几个数的和等于给定数？（ Python 实现）

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 2503 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

报账

Python

指点迷津

脚本

18 条回复 • 2018-01-16 13:19:21 +08:00

neosfung

2018-01-15 23:42:27 +08:00

3sum?

holajamc

2018-01-16 00:06:21 +08:00

https://gist.github.com/jamcplusplus/5d7b9969f1abb9592c13db193d3445bd
写的贼丑，算抛砖引玉啦

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 via iPhone

naive 的动态规划对付这个问题应该已经够了吧…

ericls

2018-01-16 02:52:31 +08:00

https://gist.github.com/ericls/1bbc72f9501a18dc6177d25c3e09a15a

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 via iPhone

@gnaggnoyil 对于日常情况来说给定数常常远小于 2^条目数

@holajamc #9 为什么？

holajamc

2018-01-16 12:29:37 +08:00

@geelaw
我感觉动态规划已经不符合楼主的『小脚本』的需求了，即使暴力穷举也能在短时间内满足其需求

geelaw

2018-01-16 12:37:16 +08:00 via iPhone

@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

是要求方案数，还是输出所有方案，还是求是否存在。说清楚。不然没人能给你正确答案。