java - 试图弄清楚要使用什么算法

Question

您输入了 n 个游戏。每个游戏都有名气(可以是负数)和先决条件游戏(必须在玩当前游戏之前玩这些游戏)。

您想找到通过玩一组有效游戏可以获得的最大名声。

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

有什么想法吗？

Answer 1

您是否有可以玩的游戏数量上限？然后，这听起来像是背包问题的变体 http://en.wikipedia.org/wiki/Knapsack_problem (在文章 k 中找到一些解决问题的方法，即使该问题是 NP 完全问题，因此原则上无法有效解决)。

如果您可以随心所欲地玩游戏，那么从计算的角度来看，这仍然很难。对于每个必备游戏，您可以通过添加它启用的游戏的知名度来计算您通过玩它获得的积分数。当然，这些会随着您玩的每个先决条件而变化，因为后来的先决条件可能会启用由较早的先决条件启用的游戏，从而减少它们提供的名声。我猜您仍然坚持为 p 个必备游戏尝试所有 2^p 组合。