真正的背包问题
提问于 2012-10-03 06:30:00
给定的
- 商品数量N
- 每个好权重N的正权重
- 每一个好利润的正利润N
- 以及一个正数W，它是背包容量。
这个问题被称为“零一背包”，用于为容量有限的背包选择最有益的商品。
示例：
- 货物(物品)数量:5
- 每项(公斤)的重量：{2、3、5、7、8}，适用于第1项第2项、.项目5按该顺序排列
- 每个项目的价值(10,000日元)：{2，4，8，9，10}，适用于第1项，第2项，.项目5按该顺序排列
- 背包容量: 10公斤
在这五种货物中：
Goods chosen Total weight Total value
Goods 1, 2 and 3 2 + 3 + 5 = 10 2 + 4 + 8 = 14 <- Maximum
回答 1
Code Golf用户
发布于 2012-10-20 17:29:48
Python，236个字符
好吧，我想我会咬人的。
from itertools import *
def k(w,p,c):
n=len(w)
r=range(n)
return max(filter(lambda y:y[1]<=c,[(s,sum(map(lambda y:w[y],s)),sum(map(lambda y:p[y],s))) for s in chain.from_iterable(combinations(r,u) for u in r+[n])]),key=lambda y:y[2])[0]使用
k函数包含三个参数:包含权重的列表、包含利润的列表和背包的容量。考虑到上面的例子，下面是如何调用它：
> print k([2,3,5,7,8], [2,4,8,9,10], 10)
(0, 1, 2)这意味着项目0、1和2是最佳解决方案。
页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/8586
复制相关文章
点击加载更多
腾讯云开发者
