小编Ken*_*nny的帖子

我正在尝试为这个问题提出一个合理的算法:

假设你有一堆球.每个球至少有一种颜色,但也可以是多色的.每个球上都有一个数字.还有一堆盒子,每个盒子只有一种颜色.目标是最大化盒子中球的数字总和,唯一的规则是:

• 为了将球放在盒子里,它必须至少在盒子上有颜色
• 你只能在每个盒子里放一个球.

例如,您可以将蓝色和绿色球放入蓝色框或绿色框中,但不能放入红色框中.

我想出了一些在运行时间方面有很大帮助的优化.例如,您可以按点值的降序对球进行排序.然后,当你从最高数字到最低数字,如果球只有一种颜色,并且没有其他高点球包含那种颜色,你可以把它放在那个盒子里(从而从那个盒子中取出那个盒子和那个球)剩下的组合).

我只是好奇是有这种类型的问题的某种动态算法,或者它只是伪装的旅行推销员问题.如果我知道最多有X种颜色会有用吗？任何帮助是极大的赞赏.谢谢!

编辑 - 这是一个简单的例子:

球:

• 1个红球--5分
• 1个蓝球 - 3分
• 1个绿色/红色球 - 2分
• 1个绿色/蓝色球 - 4分
• 1个红色/蓝色球 - 1个点

盒:

• 1红色
• 1蓝色
• 1绿色

最优方案:

• 在红色框中的红球
• 在蓝色框中的蓝色球

• 绿色框中的绿色/蓝色球

  总价值:12分(5 + 3 + 4)

假设我正在玩10种不同的游戏.对于每个游戏,我都知道获胜的概率,搭售的概率和失败的概率(每个游戏都有不同的概率).

从这些值,我可以计算赢得X游戏的概率,丢失X游戏的概率,以及绑定X游戏的概率(X = 0到10).

我只想弄清楚赢得W游戏,打T游戏以及在玩了所有10场比赛后失去L游戏的概率......并且希望比O(3 ^ n)更好.例如,获胜7,失去2和搭售1的概率是多少？

有任何想法吗？谢谢!

编辑 - 这里是一些示例数据,如果只有2个游戏:

第1场比赛:

• 胜利:23.3%
• 平局:1.1%
• 输掉:75.6%

第2场比赛:

• 胜利:29.5%
• 平局:3.2%
• 输掉:67.3%

基于此,我们可以计算出2场比赛后的概率:

• 0胜:54.0%
• 1胜:39.1%
• 2胜:6.9%

• 0关系:95.8%
• 1领带:4.2%
• 2个关系:0.0%

• 0亏:8.0%
• 1次亏损:41.1%
• 2次亏损:50.9%

根据这些数字,是否有一个通用的公式来找出W胜利,T领带和L损失的概率？可能的结果(WLT)将是:

• 2-0-0
• 1-1-0
• 1-0-1
• 0-1-1
• 0-2-0
• 0-0-2