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
hactf
V2EX  ›  Python

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

  •  
  •   hactf · 2018-01-15 23:20:58 +08:00 · 6673 次点击
    这是一个创建于 2263 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    @holajamc #9 为什么?
    holajamc
        14
    holajamc  
       2018-01-16 12:29:37 +08:00
    @geelaw
    我感觉动态规划已经不符合楼主的『小脚本』的需求了,即使暴力穷举也能在短时间内满足其需求
    geelaw
        15
    geelaw  
       2018-01-16 12:37:16 +08:00 via iPhone
    @holajamc 是你觉得动态规划太复杂,但其实并非如此
    holajamc
        16
    holajamc  
       2018-01-16 12:41:42 +08:00
    @geelaw
    我没有讲过动态规划复杂,相反我也在实际的代码中使用
    但我仍然没有觉得楼主的需求有**任何**必要使用动态规划
    ykk
        17
    ykk  
       2018-01-16 13:01:24 +08:00
    这个 leetcode 有吧 小脚本建议穷举
    maggch
        18
    maggch  
       2018-01-16 13:19:21 +08:00
    是要求方案数,还是输出所有方案,还是求是否存在。说清楚。不然没人能给你正确答案。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5438 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 08:48 · PVG 16:48 · LAX 01:48 · JFK 04:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.