python 老王装货

[ebony0319]

原文是这样的：

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

首先，是快捷的时效服务。自有专机和 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 也不知道是哪里出问题了。欲哭无泪。

[ebony0319]

我自己知道了。只取到了组合结果，但是没有取到最优化结果。

[ppwangs]

这玩意我能想到的就是穷举，从第一个开始，和后面的数字逐个相加，然后找出最接近的

[cheetah]

看了代码风格就不想读了（忽略我

[carilove]

4991?

[aheadlead]

这 tm 不就是个背包问题吗

推荐《背包九讲》

[Mistwave]

补上链接 http://love-oriented.com/pack/Index.html
做这题看第一讲 0-1 背包就行了

[freestyle]

动态规划问题不能用几个 if else 解决的

[Magic347]

重温一下当年那个熟悉的递推公式：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
dp[i][j]表示考查到第 i 个物品且背包容量为 j 时，背包所具有的最大价值

[Magic347]

PS: 当然这个问题规模并不大，穷举的复杂度也不过是 O(2^15)

[q397064399]

动态规划问题，找到递推公式，然后打标记，
这种问题 if else 搞不定的，

[q397064399]

说错了不是 if else 搞不定，如果问题规模不大的时候，

穷举的是比较好 而且比较明智的算法

[q397064399]

@Magic347
穷举的复杂度应该是 C(15/1)+C(15/2)+ ... +C(15/15)

我不知道结果是不是 O(2^15) ，高中数学没学好，别见怪

[Magic347]

@q397064399 (a+b)^n 二项式展开一下就是你的结果，其中， a = b = 1

[q397064399]

@Magic347 好吧，我果然高中数学忘光了 ^_^

[q397064399]

@Magic347 讲道理，遇到这种问题，
我还真是喜欢穷举，一来是简单，二来，问题规模不大的时候，前者易懂
也不容易写错，调试也方便

[Magic347]

@q397064399 所谓穷举无非就是穷举每个物品取或者不取的所有组合情况。
对每个物品而言，取或者不取意味着具有 2 中不同的状态，
所以如果有 n 个物品，所有状态的组合自然就是 2^15 种，对吧？
穷举的实现方式就很多了，可以搜索，也可以枚举， etc. 就看个人的习惯了。

[czheo]

[838, 793, 564, 651, 697, 747, 701]
sum = 4991
https://gist.github.com/czheo/42082a6d42223054ba1be41edf1f7ab1

[glasslion]

现在的程序员连背包问题都不知道了吗

[jedihy]

这个代码是典型的背包贪心错误。

[jedihy]

```
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]

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]

这个问题等价于从一个集合中选取一个最大子集和问题，是一个 NP 问题，找最优值恐怕只能穷举。贪心算法恐怕只能达到一定的近似度。

[yangxg]

当然也等价于背包问题，可以使用背包问题的经典动态规划算法，一般的输入规模还是能较快算出结果的。