我正在尝试为这个问题设计一个合理的算法:
假设你有一堆球。每个球至少有一种颜色,但也可以是多色的。每个球上还有一个数字。还有很多只盒子,每只盒子都只有一种颜色。目标是最大化盒子中球上数字的总和,唯一的规则是:
- 为了把一个球放进一个盒子里,它必须至少有盒子的颜色。 - 你只能在每个盒子里放一个球。
例如,你可以把一个蓝色和绿色的球放进一个蓝色或绿色的盒子里,但不能放进一个红色的盒子里。
我已经想出了一些优化方法,可以大大减少运行时间。例如,你可以按点数降序排序球。然后从最高点数到最低点数遍历,如果球只有一种颜色,并且没有其他包含该颜色的更高点数的球,你可以把它放进那个盒子里(从而删除剩余组合中的该盒子和该球)。
我只是好奇是否有某种动态算法可以解决这类问题,或者它只是旅行推销员问题的伪装。如果我知道最多有X种颜色,会有帮助吗?非常感谢任何帮助。谢谢!
简单例子:
球:
- 1个红球 - 5分 - 1个蓝球 - 3分 - 1个绿/红球 - 2分 - 1个绿/蓝球 - 4分 - 1个红/蓝球 - 1分
盒子:
- 1个红 - 1个蓝 - 1个绿
最优解:
- 红球放在红盒子里 - 蓝球放在蓝盒子里 - 绿/蓝球放在绿盒子里
总价值:12分(5 + 3 + 4)
假设你有一堆球。每个球至少有一种颜色,但也可以是多色的。每个球上还有一个数字。还有很多只盒子,每只盒子都只有一种颜色。目标是最大化盒子中球上数字的总和,唯一的规则是:
- 为了把一个球放进一个盒子里,它必须至少有盒子的颜色。 - 你只能在每个盒子里放一个球。
例如,你可以把一个蓝色和绿色的球放进一个蓝色或绿色的盒子里,但不能放进一个红色的盒子里。
我已经想出了一些优化方法,可以大大减少运行时间。例如,你可以按点数降序排序球。然后从最高点数到最低点数遍历,如果球只有一种颜色,并且没有其他包含该颜色的更高点数的球,你可以把它放进那个盒子里(从而删除剩余组合中的该盒子和该球)。
我只是好奇是否有某种动态算法可以解决这类问题,或者它只是旅行推销员问题的伪装。如果我知道最多有X种颜色,会有帮助吗?非常感谢任何帮助。谢谢!
简单例子:
球:
- 1个红球 - 5分 - 1个蓝球 - 3分 - 1个绿/红球 - 2分 - 1个绿/蓝球 - 4分 - 1个红/蓝球 - 1分
盒子:
- 1个红 - 1个蓝 - 1个绿
最优解:
- 红球放在红盒子里 - 蓝球放在蓝盒子里 - 绿/蓝球放在绿盒子里
总价值:12分(5 + 3 + 4)