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

python 老王装货

  •  
  •   ebony0319 · 2016-12-08 11:50:48 +08:00 · 4310 次点击
    这是一个创建于 2906 天前的主题,其中的信息可能已经有所发展或是发生改变。

    原文是这样的:

    顺丰速运,全货机专机运输,提供高效的便捷服务,更快更安全!

    首先,是快捷的时效服务。自有专机和 400 余条航线的强大航空资源以及庞大的地面运输网络,保障客户的快递在各环节最快发运。

    其次,是安全的运输服务。顺丰速运自营的运输网络,给消费者提供标准、高质、安全的服务。

    由此,顺丰速运在消费者的心中留下了完美的形象,从而提高了企业的业绩,也奠定了其在整个快递领域中的基础。

    顺丰快递每天能收到成千上万的物流单,每个物流单的重量不一。 现在顺丰快递的货车司机隔壁老王开着顺丰的标配货车(限载 5 吨,含 5 吨,不考虑限高),想要一次性拿走尽可能重的货物,这些货有红木沙发,有钢材等等。

    以下是货物清单:

    货物编号 货物重量(单位:kg) 1 509 2 838 3 924 4 650 5 604 6 793 7 564 8 651 9 697 10 649 11 747 12 787 13 701 14 605 15 644

    然后给上我的代码。

    l=[509,838,924,650,604,793,564,651,697,649,747,787,701,605,644]
    maxs=0
    def getnum(i,num):
        if i>=14 and l[14]+num>5000:
            return num
        elif i>=14 and l[14]+num<=5000:
            return num+l[14]        
        if l[i]+num>5000:
            return getnum(i+1,num)
        else:
            return getnum(i+1,num+l[i])
    for i in range(len(l)):
        temp=getnum(i,0)
        if temp>maxs:
            maxs=temp
    print (maxs)
    

    但是算出来 4978 也不知道是哪里出问题了。欲哭无泪。

    23 条回复    2016-12-09 08:57:39 +08:00
    ebony0319
        1
    ebony0319  
    OP
       2016-12-08 12:02:52 +08:00
    我自己知道了。只取到了组合结果,但是没有取到最优化结果。
    ppwangs
        2
    ppwangs  
       2016-12-08 12:02:54 +08:00
    这玩意我能想到的就是穷举,从第一个开始,和后面的数字逐个相加,然后找出最接近的
    cheetah
        3
    cheetah  
       2016-12-08 12:03:19 +08:00
    看了代码风格就不想读了(忽略我
    carilove
        4
    carilove  
       2016-12-08 12:20:24 +08:00
    4991?
    aheadlead
        5
    aheadlead  
       2016-12-08 12:22:19 +08:00
    这 tm 不就是个背包问题吗

    推荐《背包九讲》
    Mistwave
        6
    Mistwave  
       2016-12-08 12:34:41 +08:00 via iPhone   ❤️ 1
    补上链接 http://love-oriented.com/pack/Index.html
    做这题看第一讲 0-1 背包就行了
    freestyle
        7
    freestyle  
       2016-12-08 12:38:24 +08:00 via iPhone
    动态规划问题不能用几个 if else 解决的
    Magic347
        8
    Magic347  
       2016-12-08 13:44:23 +08:00
    重温一下当年那个熟悉的递推公式:
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
    dp[i][j]表示考查到第 i 个物品且背包容量为 j 时,背包所具有的最大价值
    Magic347
        9
    Magic347  
       2016-12-08 13:48:18 +08:00
    PS: 当然这个问题规模并不大,穷举的复杂度也不过是 O(2^15)
    q397064399
        10
    q397064399  
       2016-12-08 14:02:23 +08:00
    动态规划问题,找到递推公式,然后打标记,
    这种问题 if else 搞不定的,
    q397064399
        11
    q397064399  
       2016-12-08 14:06:02 +08:00
    说错了不是 if else 搞不定,如果问题规模不大的时候,

    穷举的是比较好 而且比较明智的算法
    q397064399
        12
    q397064399  
       2016-12-08 14:12:55 +08:00
    @Magic347
    穷举的复杂度应该是 C(15/1)+C(15/2)+ ... +C(15/15)

    我不知道结果是不是 O(2^15) ,高中数学没学好,别见怪
    Magic347
        13
    Magic347  
       2016-12-08 14:15:33 +08:00
    @q397064399 (a+b)^n 二项式展开一下就是你的结果,其中, a = b = 1
    q397064399
        14
    q397064399  
       2016-12-08 14:17:32 +08:00
    @Magic347 好吧,我果然高中数学忘光了 ^_^
    q397064399
        15
    q397064399  
       2016-12-08 14:20:03 +08:00
    @Magic347 讲道理,遇到这种问题,
    我还真是喜欢穷举,一来是简单,二来,问题规模不大的时候,前者易懂
    也不容易写错,调试也方便
    Magic347
        16
    Magic347  
       2016-12-08 14:20:40 +08:00
    @q397064399 所谓穷举无非就是穷举每个物品取或者不取的所有组合情况。
    对每个物品而言,取或者不取意味着具有 2 中不同的状态,
    所以如果有 n 个物品,所有状态的组合自然就是 2^15 种,对吧?
    穷举的实现方式就很多了,可以搜索,也可以枚举, etc. 就看个人的习惯了。
    czheo
        17
    czheo  
       2016-12-08 15:17:09 +08:00   ❤️ 1
    [838, 793, 564, 651, 697, 747, 701]
    sum = 4991
    https://gist.github.com/czheo/42082a6d42223054ba1be41edf1f7ab1
    glasslion
        18
    glasslion  
       2016-12-08 15:21:23 +08:00
    现在的程序员连背包问题都不知道了吗
    jedihy
        19
    jedihy  
       2016-12-08 16:02:59 +08:00
    这个代码是典型的背包贪心错误。
    jedihy
        20
    jedihy  
       2016-12-08 16:38:54 +08:00
    ```
    v = [509,838,924,650,604,793,564,651,697,649,747,787,701,605,644]
    dp = [0] * 5001

    for i in xrange(0, len(v)):
    for j in reversed(xrange(1, 5001)):
    if j - v[i] >= 0:
    dp[j] = max(dp[j], dp[j - v[i]] + v[i])
    print dp[-1]


    ```
    jedihy
        21
    jedihy  
       2016-12-08 16:39:59 +08:00   ❤️ 1
    v = [509,838,924,650,604,793,564,651,697,649,747,787,701,605,644]
    dp = [0] * 5001

    for i in xrange(0, len(v)):
    for j in reversed(xrange(1, 5001)):
    if j - v[i] >= 0:
    dp[j] = max(dp[j], dp[j - v[i]] + v[i])
    print dp[-1]
    yangxg
        22
    yangxg  
       2016-12-09 08:55:16 +08:00
    这个问题等价于从一个集合中选取一个最大子集和问题,是一个 NP 问题,找最优值恐怕只能穷举。贪心算法恐怕只能达到一定的近似度。
    yangxg
        23
    yangxg  
       2016-12-09 08:57:39 +08:00
    当然也等价于背包问题,可以使用背包问题的经典动态规划算法,一般的输入规模还是能较快算出结果的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5129 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 09:32 · PVG 17:32 · LAX 01:32 · JFK 04:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.