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

TNT嗼嗼
  • 2
新手上路,请多包涵

有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

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

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

回复
阅读 882
2 个回答
TNT嗼嗼
  • 2
新手上路,请多包涵

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

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

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏