自动编成问题(1)

问题的提出

在很多游戏（特别是卡牌游戏）都会有一个deck的概念。 所谓deck，即为一些角色的组合（卡牌游戏中又称”卡组”）。在游戏中通常以一个整体存在。 当然游戏不同，叫法也不一样，以下均用deck指代。

deck配置的优劣经常在战斗中起着非常重要的作用。 但是对于非核心玩家来说，配置deck的过程常常因为过于繁琐而让这些玩家望而却步。 因此大多数需要配置deck的游戏中都会带有”自动编成”的功能，以便于玩家简单的配置出一个deck。

本文在此讨论比较典型的几种。

在讨论具体问题之前首先定义评价一个deck好坏的指标。 本文中一律使用deck中角色攻击力的总和作为衡量一个deck的分数。 当然deck编成时反映的攻击力并不代表战斗时候的实际强弱。 这里只是为了容易评估而进行的简化操作。

deck自动编成的目的是：给玩家配置出尽可能“强”的组合。 形式化的描述为：从备选的n个角色中选出m(m为deck的可放置数)个角色，使得所选角色的攻击力总和sum(a)最大。

这种最最简单的抽象其实是个简单的背包问题。 然而随着游戏不同，对于问题的定义和附加条件也会随之改变，解决方法也不尽相同。 为了便于讨论，以下按几个关键要素将问题进行分类。

按照deck编成时除了角色个数上限之外是否有其他限制可以分为：

• 有附加限制deck
• 无附加限制deck

按照deck编成时角色之间是否有相互的加成可以分为：

• 有相互作用deck
• 无相互作用deck

无附加限制 + 无相互作用deck

这是最简单的一类，答案没有任何悬念：贪心法。
直接选择从n个角色中选择攻击力最高的m个配置即可。

有附加限制 + 无相互作用deck

接着我们稍微提高一点难度。

关于附加限制，我们只讨论最简单的一种——cost限制。 所谓cost限制，即每个角色都存在一个cost值，所选角色的cost值综合不能够超过deck cost的最大上限。

这其实是0-1背包问题，得到最优解需要用动态规划算法。

无附加限制 + 有相互作用deck

这一类问题已经开始接近真实的游戏设定了。

对于相互作用，我们这里定义为角色i和j如果同时出现在deck上，会导致deck中的某些角色攻击力上升b%。
这个条件的引入使得问题一下子变复杂了——角色i会根据其他角色的出现而反映出不同的攻击力。
而且这个问题不能够使用动态规划或者贪心算法，因为这个问题没有“最优子结构”的性质。
即：即使A(m-1)是最优的，由于相互作用的存在，有A(1) … A(m-1)递推得到的A(m)不一定就是最优的。

反例如下：

假设deck有5个位置，角色的攻击力为1~5。
那么在没有任何加成的情况下的最强配置应该是：
5 5 5 5 5 总攻击力：25

现在加入相互作用，规定：

• 2个攻击力为4的角色可以获得攻击力加成200%
• 3个攻击力为3的角色可以获得攻击力加成300%
• 4个攻击力为2的角色可以获得攻击力加成500%
• 5个攻击力为1的角色可以获得攻击力加成1000%

那么配置i个角色时的最强配置为：

可见任意一个最强配置都不能由之前的最强配置递推产生。
因此这个问题不能够使用动态规划或者贪心算法。

解决方法：

最容易想到解法是穷举法。
这类方法看简单直接，可以直接求出最优解。 穷举法在解空间较小或对时间空间要求不很严格的时候的时候很好用。 如果备选个数n以及deck容量m足够小，总共的可能性有C(m, n)种，因此算法的代价是 O(C(m, n))。

虽然穷举法在m, n较小的时候可用，但是可以看到其复杂度是C(m, n)，在最坏情况下是n!的数量级。 m, n稍一扩大，代价就变得无法接受了。
因此必须考虑其他的解决办法。

小结：

• 具有诸如：“i和j同时在场则双方攻击力加b%”的性质的问题是不满足最优子结构性质的。 因而不能够使用动态规划或者贪心算法。