python 老王装货

2016-12-08 11:50:48 +08:00
 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 也不知道是哪里出问题了。欲哭无泪。

4241 次点击
所在节点    Python
23 条回复
jedihy
2016-12-08 16:39:59 +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]
yangxg
2016-12-09 08:55:16 +08:00
这个问题等价于从一个集合中选取一个最大子集和问题,是一个 NP 问题,找最优值恐怕只能穷举。贪心算法恐怕只能达到一定的近似度。
yangxg
2016-12-09 08:57:39 +08:00
当然也等价于背包问题,可以使用背包问题的经典动态规划算法,一般的输入规模还是能较快算出结果的。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/326136

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX