Welcome toVigges Developer Community-Open, Learning,Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
226 views
in Technique[技术] by (71.8m points)

背包问题变种,有思路吗?

有n个按顺序放置的背包,每个背包不固定大小(入参:背包序号,背包大小)

可能有多个相同序号的背包,相同序号的背包大小固定
如 
一号背包容量120g,二号背包容量160g,三号背包容量200g,四号背包容量250g,五号背包容量400g,第二个一号背包容量120g
[{1,120},{2,160},{3,200},{4,250},{5,400},{1,120}]

有30个人,每个人手里有x种组合(每个人可选组合不同,但每种组合固定填充背包共三次),用组合方式去填充背包,每个组合样例如下:

1号组合(有10个人能用) 一号背包20g,二号背包20g,五号背包12g
2号组合(有30个人能用) 二号背包20g,四号背包20g,五号背包12g
3号组合(有20人能用)   三号背包10g,五号背包10g,五号背包12g

要求只能最后一个背包填不满,同时最后一个背包尽可能地多填,怎么填充?

在传统背包问题中减少了价值判断,但多了其他维度


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

目前几个思路:
定义收益(权重) —— 线性规划
按顺序计算背包 —— 动态规划

昨晚用回溯法,时间复杂度已经让人自闭了


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to Vigges Developer Community for programmer and developer-Open, Learning and Share
...