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:
- what kind of problem is this? It looks like a Bin packing problem, but I think it's different
- What is a good algorithm to solve it?
This is a multiobjective optimization problem.
The objectives are:
- Distribute as many boxes as possible
- All the persons uses approximately the same strength
- All the persons uses approximately the same money
and the constrains:
- Weight of each box
- Strength of each person
- Money of each person
It looks like a variation of a multiple-constraints multiple-nested-knapsack problem.
精彩评论