# Derive a algorithm to match best position

I have pieces in my game which have stats and cost assigned to them and they can only be placed at a certain location.

Lets say I have 50 pieces.

e.g. Piece1 = 100 stats, 10 cost, Position A. Piece2 = 120 stats, 5 cost, Position B. Piece3 = 500 stats, 50 cost, Position C. Piece4 = 200 stats, 25 cost, Position A. and so on..

I have a board on which 12 pieces have to be allocated and have to remain inside the board cost. e.g. A board has A,B,C ... J,K,L positions and X Cost assigned to it.

I have to figure out a way to place best possible piece in the correct position and should remain within the cost specified by the board.

Any help would be appreciated.

• Looks like a trivial generalisation of the knapsack problem – Peter Taylor Jan 24 '13 at 13:12
• I think is not Knapsack problem, because there are multiple dependent variables. I think you should formulate your problem as integral linear program and then use Simplex algorithm to solve it. – Ivan Kuckir Jan 24 '13 at 15:49
• Not sure if we understand your question. You have N pieces, each with a stat and cost. There is a board with M positions. Do you mean to say that each piece takes up several positions? Or that each position on the board has an a cost? – jzx Jan 24 '13 at 16:53
• I can't make head or tail of this question. Can somebody who does understand it (OP or otherwise) edit it into something more comprehensible to the rest of us? – Trevor Powell Jan 24 '13 at 22:15
• @jzx Each piece only takes one position and the board overall has a cost. It does not depend on position. – Farooq Arshed Jan 25 '13 at 3:21

Here's what I'd do:

For each position generate a list of all possible pieces that can go there. Sort them by stats. Remove any overly expensive pieces from the lists. That is ones where there's another piece with higher or equal stats and lower cost.

To start with try the best possible piece in each position. If the score is under the limit then you're done.

If the score isn't under the limit then make sure that using the cheapest possible piece in each position gets you under the score limit. If it doesn't then it's unsolvable, otherwise this is your starting point for a search. If you don't have to put a piece in all positions then start with all positions empty.

What you need to find is the combination of substitutions that gives the biggest score increase, with a cost that keeps you within the limit. Unfortunately I believe that is the knapsack problem which is NP complete, so getting a perfect answer might take a while.

However you can use a greedy algorithm to get a quick but possibly inaccurate answer by repeatedly picking the best upgrade. That is you make the change that gives the biggest increase in stats per point of cost increase (while keeping within the cost limit).

This goes wrong in some cases. For example say you have 10 points spare, and only two possible changes left that fit the budget.

1. Gain 10 stats for 2 points. 10/2 = 5 so this is the most cost effective change.
2. Gain 20 stats for 10 points. 20/10 = 2 so this isn't very cost effective.

The ideal pick is of course the second one despite the inefficiency, because if you pick the first there's nothing you can do with those last 8 points.

However it's not too expensive when the number of options is low to just try them all (there's 2^N subsets to try). When the number of options is high, hopefully you aren't close enough to the cost limit for the result to benefit significantly from a full search.

OK I believe I got this, I would start with the following.

For each position
divide the total cost for board by number of positions left to fill.
get best possible player for this position based on value above.
return the highest stats unit with cost thats under the amount allowed
remove cost of from total cost.
set player chosen for this position.


This would mean that at every point we recheck the max cost for a player for a position, By changing the definition of best player you can manipulate how placement is done.