推荐学习书目 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
这是一个创建于 3234 天前的主题，其中的信息可能已经有所发展或是发生改变。
原文是这样的：
顺丰速运，全货机专机运输，提供高效的便捷服务，更快更安全!
首先，是快捷的时效服务。自有专机和 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 也不知道是哪里出问题了。欲哭无泪。
 | 1 ebony0319 OP 我自己知道了。只取到了组合结果，但是没有取到最优化结果。 |
 | 2 ppwangs 2016-12-08 12:02:54 +08:00 这玩意我能想到的就是穷举，从第一个开始，和后面的数字逐个相加，然后找出最接近的 |
 | 3 cheetah 2016-12-08 12:03:19 +08:00 看了代码风格就不想读了（忽略我 |
 | 4 carilove 2016-12-08 12:20:24 +08:00 4991? |
 | 5 aheadlead 2016-12-08 12:22:19 +08:00 这 tm 不就是个背包问题吗 推荐《背包九讲》 |
 | 6 Mistwave 2016-12-08 12:34:41 +08:00 via iPhone  1 补上链接 http://love-oriented.com/pack/Index.html 做这题看第一讲 0-1 背包就行了 |
 | 7 freestyle 2016-12-08 12:38:24 +08:00 via iPhone 动态规划问题不能用几个 if else 解决的 |
 | 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 时，背包所具有的最大价值 |
| 9 Magic347 2016-12-08 13:48:18 +08:00 PS: 当然这个问题规模并不大，穷举的复杂度也不过是 O(2^15) |
 | td width="auto" valign="top" align="left"> |
| 11 q397064399 2016-12-08 14:06:02 +08:00 说错了不是 if else 搞不定，如果问题规模不大的时候， 穷举的是比较好 而且比较明智的算法 |
| 12 q397064399 2016-12-08 14:12:55 +08:00 |
| 13 Magic347 2016-12-08 14:15:33 +08:00 @q397064399 (a+b)^n 二项式展开一下就是你的结果，其中， a = b = 1 |
| 14 q397064399 2016-12-08 14:17:32 +08:00 @Magic347 好吧，我果然高中数学忘光了 ^_^ |
| 15 q397064399 2016-12-08 14:20:03 +08:00 |
| 16 Magic347 2016-12-08 14:20:40 +08:00 @q397064399 所谓穷举无非就是穷举每个物品取或者不取的所有组合情况。 对每个物品而言，取或者不取意味着具有 2 中不同的状态， 所以如果有 n 个物品，所有状态的组合自然就是 2^15 种，对吧？ 穷举的实现方式就很多了，可以搜索，也可以枚举， etc. 就看个人的习惯了。 |
 | 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 |
 | 18 glasslion 2016-12-08 15:21:23 +08:00 现在的程序员连背包问题都不知道了吗 |
 | 19 jedihy 2016-12-08 16:02:59 +08:00 这个代码是典型的背包贪心错误。 |
| 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] ``` |
| 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] |
 | 22 yangxg 2016-12-09 08:55:16 +08:00 这个问题等价于从一个集合中选取一个最大子集和问题，是一个 NP 问题，找最优值恐怕只能穷举。贪心算法恐怕只能达到一定的近似度。 |
| 23 yangxg 2016-12-09 08:57:39 +08:00 当然也等价于背包问题，可以使用背包问题的经典动态规划算法，一般的输入规模还是能较快算出结果的。 |
Select Language