关于个人能力的资源分配 - 这是背包问题吗?
我有一个问题如下:
- 我的办公地点和资源具有不同的功能(整数)。
- 我想把所有的资源分配到不同的办公地点,找到最好的方式,将它们几乎均等地分配到各个地点,使所有办公地点的能力尽可能平衡。需要记住以下几点:
• 每个办公地点的资源数量差异不应超过 1。 • 每个办公地点的能力(通过增加个人能力而达到)应尽可能彼此接近相等。
我在互联网上进行了研究,并了解了 Knapsack 算法和 Bin-pack 算法,这听起来与这个问题很接近。
例子: 办公地点数量 = 3; 人数=8; 人员能力=10,20,5,150,90,200,250,140(8种资源的能力值);
上述数字只是样本。它可以增长到1000+的资源和各自的能力值。办公地点的数量也可以变化。
除非我确信我要走的路是正确的,否则我不会开始编程部分。我请求您的帮助,引导我找到正确的方向来解决这个问题。
另外,如果您可以为此分享一个可能的伪代码,将会有很大的帮助。
谢谢!
I have a problem as follows:
- I have few office locations and resources with different capabilities (integer numbers).
- I want to distribute all the resources to different office locations to find the best way to divide them almost equally among the locations so that the capabilities of all the office locations are balanced as much as possible. Couple of things to keep in mind:
• Difference between number of resources in each office location should not be more than one.
• The capability of each office location (reached by adding individual capability) should be nearly equal as possible to each other.
I have researched over the internet and came to know about Knapsack algorithm and Bin-pack algorithm which sounds close to this problem.
Example:
Number of office locations = 3;
Number of people = 8;
People capability = 10, 20, 5, 150, 90, 200, 250, 140 (capabilities values of the 8 resources);
The above numbers are just sample. It can grow to 1000+ for resources and respective capabilities value. Number of office locations can be varied too.
I didn't start the programming part unless I am sure that the path that I am going to take it correct. I am requesting your help to guide me to a correct direction to solve this.
Also, if you can share a probable pseudo code for this, will be a great help.
Thanks!
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
这就是背包问题,或者至少同样困难(考虑只有两个办公室的情况),因此获得最佳解决方案将非常困难。您可以尝试使用一些通用的优化启发式方法,例如模拟退火: http://en.wikipedia.org/wiki/模拟退火
This is the knapsack problem or is at least as difficult (consider an instance where there are only two offices), so obtaining the best solution will be very difficult. You may try to use some generic optimization heuristic like simulated annealing: http://en.wikipedia.org/wiki/Simulated_annealing