algorithm - 寻找在海军交战中瞄准船只的最佳解决方案

Question

我有一个由 n 和 m 艘船组成的舰队之间的交战，友方舰队中的每艘船都有自己的 Volley 伤害，而敌方舰队中的每艘船都有自己的生命值。该算法的目标是找到最佳解决方案(如果存在这样的解决方案)以将目标分配给您的船只(例如:我舰队中的舰船 1 目标是您舰队中的舰船 3)，以使 Volley 最大化对敌方舰队造成的伤害量。

重要。所谓伤害，是指被摧毁的敌舰的​​伤害量/生命值。如果一艘敌舰有 100hp 并造成 20dmg，它的“值(value)”是 100/20 = 5。所以摧毁那艘船会得到 5 分。最后，只考虑被摧毁船只的分数。如果不可能用一次 Volley 摧毁任何船只，则分数将包括损坏的船只。

我也尝试过贪心法、迭代改进法、爬山法，但都不能达到最优解。我还尝试过另一种方法，即制作并评估大量随机目标选择集，然后从中选出最好的一个。这是产生了最佳结果的方法，但它的效率低得令人难以置信，而且几乎从未产生过最佳结果。

我相信必须有一种方法可以计算出不需要检查每一个可能的目标选择的最佳解决方案，但我找不到这样做的方法。这个问题似乎也像是多背包问题的一种奇怪形式。背包是敌人的生命值池，元素是射击的伤害值。除了这次放入背包的最后一件元素可以超过背包的大小限制，但只有适合背包的元素值(value)的一小部分才有用。

即使不能解决问题，我们也非常感谢任何想法或帮助!

Answer 1

Linear programming会在这里完美地完成工作。在这种情况下，决策变量是整数，所以我们处理的是ILP。 .
以下是关于如何将您的问题建模为线性程序的简短说明。

Data:
F_dmg[n] // an array containing the damage of friendly ships
E_hp[m]  // an array containing the hp points of the ennemy ships
M        // constant, the highest hp among all ships
V[m]     // the 'value' of ennemy ships


Decision variables:
X[n][m]     // a matrix of booleans (0 or 1)
            // X[i][j] = 1 if the ship i attacks the ship j, 0 otherwise
Dmg[m]      // an array of integer, representing the total damage taken by each ennemy ship
IsAlive[m]  // an array of booleans, representing the fact that the ship is destroyed or not (0 if dead, 1 if alive)


Constraints:
// a friend ship can attack at most one ennemy ship
for all i in 1..n, sum(j in 1..m) X[i][j] <= 1
// the damage sustained by a ship cannot exceed its hp
for all j in 1..m, sum(i in 1..n) Dmg[m] <= E_hp[j]
// the damage sustained by a ship has to be coherent with the attacks it receives
for all j in 1..m, sum(i in 1..n) Dmg[j] <= X[i][j] * F_dmg[i]
// a ship is destroyed if the damage sustained is equal to its hp
for all j in 1..m, M * IsAlive[j] >= E_hp[j] - Dmg[j] 


Objective function
maximize sum(j in 1..m) (1 - IsAlive[j]) * V[j]

在 OPL 中编写，将其提供给 ILP 求解器，如果您的输入不是绝对巨大，您将很快获得最佳答案。