Ken*_*nny 10 algorithm optimization mathematical-optimization traveling-salesman np
我正在尝试为这个问题提出一个合理的算法:
假设你有一堆球.每个球至少有一种颜色,但也可以是多色的.每个球都有一个重量和一个与之相关的值.还有一堆盒子,每个盒子只有一种颜色.每个盒子都有最多可以容纳的球.目标是在保持总重量W的同时最大化盒子中的值的总和,唯一的规则是:
为了将球放入盒子中,它必须至少具有盒子的颜色
(例如,您可以将蓝色和绿色球放入蓝色框或绿色框中,但不能放入红色框中.)
我已经进行了一些研究,这看起来类似于背包问题,也类似于匈牙利算法可以解决,但我似乎无法将其减少到任何一个问题.
我只是好奇是有这种类型的问题的某种动态编程算法使它在多项式时间内可解决,或者它只是伪装的旅行推销员问题.如果我知道最多有X种颜色会有用吗？任何帮助是极大的赞赏.如果它有帮助,我也可以用变量名称来形式化这个问题.谢谢!
这是一个简单的例子:
最大重量: 5
球:
1个红球 - (值= 5,重量= 1)
1个蓝色球 - (值= 3,重量= 1)
1个绿色/红色/蓝色球 - (值= 2,重量= 4)
1个绿色/蓝色球 - (值= 4,重量= 1)
1个红色/蓝色球 - (值= 1,重量= 1)
盒:
1红色(1个球)
1蓝色(可容纳2个球)
1绿色(持1个球)
最优方案:
在红色框中的红球
蓝色的球和蓝色框中的红色/蓝色球
绿色框中的绿色/蓝色球
总价值:13(5 + 3 + 1 + 4)
总重量:4(1 + 1 + 1 + 1)
注意:即使绿色/红色/蓝色球比红色/蓝色球更有价值,它的重量也会让我们超过极限.
编辑:
一个澄清点:具有相同颜色组合的球不一定具有相同的重量和值.例如,你可以有一个值为3且重量为1的红色球和另一个值为2且重量为5的红色球.
编辑2:
如果它有助于我们提出动态编程算法,我们可以假设整数权重和值.
这至少和背包问题一样复杂 - 考虑所有球都是红色并且只有一个红色框的情况.
如果具有相同颜色组合的球必须具有相同的重量和值,请考虑具有红色/蓝色,红色/绿色等球和仅一个红色框的情况.