1

You have an input a n games. Each game has a fame (which can be negative) and prerequisite games (these games must be played before you play the current game).

You want to find the maximum amount of fame you can gain by playing a valid set of games.

One idea I had was to use a weighted directed graph however you still have to try every single pair of nodes in the graph to find the optimal solution.

Any ideas?

Improve this question
4
  • 2
    With the description of the problem given, it sounds like playing all games is always the best solution. Commented May 1, 2011 at 21:45
  • 1
    @Simon: No, some games may have negative fames (ie.: costs) associated with them. Commented May 1, 2011 at 22:13
  • Do you have any information on how big n can be? Commented May 1, 2011 at 22:33
  • N is less than or equal to 1000. Commented May 1, 2011 at 23:39

3 Answers 3

Reset to default
2

Do you have a maximum number of games you can play? Then, it sounds like a variant of the Knapsack problem http://en.wikipedia.org/wiki/Knapsack_problem (find some approaches to the problem in the articlek, even though the problem is NP-complete and as such not efficiently solvable in principle).

If you can play as many games as you like, well it's still hard in a computational sense. For each prerequisite game, you can compute the number of points you gain by playing it by adding the fame of the games it enables. Of course these change with each prerequisite you play because later prerequisites may enable games that have been enabled by earlier prerequisites, decreasing the gain in fame they provide. I guess you're still stuck with trying out all 2^p combinations for p prerequisite games.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Maybe an A* algorithm would help you here, i.e. you'd make an educated guess (minimum fame for that route) for each route in your graph, follow the most promising one and if you see it gets lower than a guess for a route not taken yet, follow that new route and stop here.

Improve this answer

Comments

0

The approach below will work for graphs with non-negative edges: Since there are dependencies between games, the graph is acyclic. You can negate all the edges in the graph and find the shortest path in P-time. This then gives the longest path in the original graph.

Edit:

Since, the graph is acyclic the shortest path will work for negative edges also. See Shortest / longest path in a DAG in http://algs4.cs.princeton.edu/44sp/

Improve this answer

4 Comments

I was thinking using Bellman Ford which works with negative edges.
@Reflux, yes that will work. You'll need to repeat with each game as a source to find the longest path.
Finding paths doesn't solve the problem. Consider 4 games, A, B, C, D. B, C and D depent on A. A has -2 fame, while B, C, D have fame +1. The largest paths to be found have total fame -1 (so are not good), but the optimal solution is taking every game.
@missingno How about this graph: (nodes: S, A, B, C, D and edges: S->[A=-2, B=1, C=1], A->[B=1, C=1, D=1], B->[A=-2, C=1], C->[A=-2, B=1], D->[B=1, C=1]). A longest path from source S should yield (one possible path) S->B->C with path weight (fame) = 2. Taking every game is not optimal!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.