开发者

Uniformely distribute as many items as possible among a set of carriers

Problem:

  • there n boxes b_1, ... b_n
  • box b_i开发者_JS百科 has weight w_i and cost c_i
  • there are m persons p_1, .... p_m
  • person p_i has strength s_i and money m_i, and so she/he can carry a number of boxes such that the sum of their weights is less than or equal to s_i, and the sum of their costs is less than or equal to m_i

How do I distribute the boxes among the persons such that the maximum number of boxes is uniformly distributed among the m persons? In other words, I want to distribute as many boxes as possible (ideally all the n boxes) among the m persons, in such a way that all the persons uses approximately the same strength to carry the weight of their respective boxes, and spend approximately the same amount of money to take them.

Questions:

  1. what kind of problem is this? It looks like a Bin packing problem, but I think it's different
  2. What is a good algorithm to solve it?


This is a multiobjective optimization problem.

The objectives are:

  1. Distribute as many boxes as possible
  2. All the persons uses approximately the same strength
  3. All the persons uses approximately the same money

and the constrains:

  1. Weight of each box
  2. Strength of each person
  3. Money of each person

It looks like a variation of a multiple-constraints multiple-nested-knapsack problem.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜