试图找出使用什么算法

你有一个输入n场比赛。每个游戏都有一个声望（可以是负面的）和必备游戏（这些游戏必须在玩游戏之前播放）。试图找出使用什么算法

你想通过玩一套有效的游戏来找到你可以获得的最大声望。

我的一个想法是使用加权有向图，但是您仍然需要尝试图中每对节点来找到最佳解决方案。

任何想法？

来源

2011-05-01 Reflux

随着所给问题的描述，听起来好像玩所有游戏始终是最佳解决方案。 – blubb 2011-05-01 21:45:48

@Simon：不，一些游戏可能会产生负面的fames（即：费用）。 – hugomg 2011-05-01 22:13:28

你有没有关于'n'有多大的信息？ – hugomg 2011-05-01 22:33:50

你有最大数量的游戏可以玩吗？然后，这听起来像背包问题的一个变种http://en.wikipedia.org/wiki/Knapsack_problem（找到问题的一些方法，即使问题是NP完全的，因此原则上不能有效解决）。

如果您可以随心所欲地玩很多游戏，那么从计算的角度来看它仍然很难。对于每个必备游戏，您可以通过添加游戏的声望来计算获得的点数。当然，这些会随着你玩的每个先决条件而改变，因为后来的先决条件可能会使先前的先决条件已启用的游戏，从而减少它们提供的名望上的增益。我想你仍然坚持尝试所有2^p组合对于p前提游戏。

来源

2011-05-01 21:38:48 Nicolas78

也许A* algorithm会帮助你，也就是说，你会为图表中的每条路线做一个有根据的猜测（对于这条路线的最小名气），请遵循最有前途的猜测，如果你看到它低于猜测还没有采取的路线，按照新的路线，并停在这里。

来源

2011-05-01 21:40:49 Thomas

A *不支持负边权重。 – shams 2011-05-01 23:13:59

下面的方法适用于具有非负边的图：由于游戏之间存在依赖关系，因此该图是非循环的。您可以否定图中的所有边并在P时间中找到最短路径。这然后给出了原始图中最长的路径。

编辑：

因为，图表是非循环的最短路径，将负边缘也行。请参阅DAG中的最短/最长路径http://algs4.cs.princeton.edu/44sp/

来源

2011-05-01 21:40:49 shams

我正在考虑使用贝尔曼福特，它与消极的边缘。 – Reflux 2011-05-01 21:48:53

@Reflux，是的，这将工作。你需要重复每场比赛作为一个来源找到最长的路径。 – shams 2011-05-01 21:51:14

查找路径不能解决问题。考虑4场比赛，A，B，C，D，B，C和D依赖A. A有-2个名望，而B，C，D有名望+1。要找到的最大路径总有名望-1（所以不太好），但最佳解决方案是每场比赛。 – hugomg 2011-05-01 22:43:37

试图找出使用什么算法

回答

相关问题