将尽可能多的物品均匀地分布在一组载体中

  • 本文关键字:一组 分布 尽可能 algorithm
  • 更新时间 :
  • 英文 :


问题

  • 有n个框b_1。。。b_n
  • 框b_i具有权重w_i和成本c_i
  • 存在m个人p1。。。。p_m
  • 人p_i有力量s_i和金钱m_i,因此她/他可以携带多个箱子,使得它们的重量之和小于或等于s_i,并且它们的成本之和小于等于m_i

如何在人员之间分配箱子,使最大箱子数量均匀分布在m人之间?换言之,我想在m个人中分配尽可能多的盒子(理想情况下是所有n个盒子(,这样所有人都使用大致相同的力量来承载各自盒子的重量,并花费大致相同的钱来拿走它们。

问题

  1. 这是什么问题?这看起来像是垃圾箱的包装问题,但我认为不同
  2. 什么是解决它的好算法

这是一个多目标优化问题。

目标是:

  1. 分发尽可能多的盒子
  2. 所有人使用的力量大致相同
  3. 所有人使用的钱大致相同

以及限制条件:

  1. 每个箱子的重量
  2. 每个人的力量
  3. 每人的钱

它看起来像是多约束多嵌套背包问题的一个变体。

最新更新