I'm not sure which Stackexchange site is best suited for this question. It's about a programming problem, but more about logic and less about coding.
I have a set of cards. These only differ in their type, cards of the same type are "the same", so you could look at the set of cards as "3x A, 2x B, 4x C, etc.". Each type has a certain maximum of cards with that color, eg. 3 A-cards, 4 B-cards, etc.. You can thus only ever have that many cards of this type.
Then I have a set of scoring rules. While the cards may change (you draw new ones, or lose some), the scoring rules stay the same throughout the game. These assign a score to combinations of cards. A card can be used for one rule only, but the rule may be applied as often as needed.
There are two kinds of scoring rules:
- Combos take the form "A + B = 40". They currently contain at least 2 types of cards up to 4, while having each type only once (no "A + A + B") - in case that matters.
- Monopolies are a form of scoring cards of the same type. Each card type has a list of integers, the length dictating how many cards of that type are available. A Monopoly rule for A may be "2,10,100", granting you 2 points for 1 card of type A, 10 for 2 cards, and 100 points for collecting all 3 A-cards. Having more of a type is always better. Having 3 A-cards only gives you 100 points, not 2+10+100.
Now I want to find out the best score that my cards can achieve. Sometimes using the Monopoly scoring yields a better score than using cards for Combos - or the other way round - so I might need to check all combinations of Monopolies and Combos. (I currently do)
I thought about this problem and came up with a solution that creates a graph, where each node is a state (remaining cards + used Combos), checking all other reachable states (by applying a Combo and removing the cards for it). If the state that would be reached by that operation is already known, we don't go for that state again. For each state, all cards that have not been put into Combos are turned into Monopolies for their type to score them. An overall score can then be calculated for the state (Combos + Monopolies). Once we tried out all possible combinations, we know which one has the highest score - goal reached!
Example:
Cards: A A B C C C D D
Combos: {A,B} = 60, {A,C,D} = 20
Monopolies: A(2,10,100), B(50), C(1,5,30), D(5,15,70)
Result: {A} = 2, {D,D} = 15, {C,C,C} = 30, {A,B} = 60
= 107
This works for few cards, but gets slower very fast as you add cards, so I was wondering if and where my algorithm can be improved, or if a better one exists.
(It gets more complex, as there are also modifier-cards, that multiply the score of a single Combo or Monopoly of a certain type, which I have solved in the same way, for each state.)
I don't quite know which tags to assign, so feel free to help me out :)
In theory it is unlikely to find an efficient algorithm, because your problem is NP-hard, here is how you can solve independent set with it:
Given graph $G = (V, E)$, we make the set $E$ our cards (each card is unique) and the set $V$ our combos, where the combo corresponding to a vertex consists of all its incident edges. All combos have a score of $1$ and there are no monopolies. The maximum attainable score gives you the independence number.
If you don't need the exact result, you might want to try linear programming, depending on your particular set of scoring rules, the integrality gap might not be very big (at the bottom of wiki page on LP you can find a list of solver libraries).
I hope this helps $\ddot\smile$