I am wanting to write a calculator for a problem in a game, but am not sure what type of algorithm/math is needed.
Problem:
I have 50 pirates, each with 4 stats (say attack, defence, intelligence, courage), with varying values.
I have 4 boats, each holding up to 5 pirates. A pirate cannot be shared between boats.
The boats have a target for 14 of these stats (boat 1 might need 800 attack and 800 defence), and another with 1200 in respective values. These targets do not have to be met, but the aim is to get as close as possible to it. Though it may be specified that the target is met.
The list of pirates and their stats, and the boats and their targets, and if they need to be met or not will be the inputs. Output should be the list of boats and their pirates which get as close to meeting all targets as possible.
The closest type of math I know similiar to this is linear programming, but without there being a continuous/plottable data set, I don't believe that can be used. I suppose it's like the knapsack problem, with multiple knapsacks, but I want to be sure.
What you do think?
Thanks
Type of Math/Algorithm needed for problem
Page 1 of 14 Replies  1286 Views  Last Post: 13 March 2013  09:59 PM
Replies To: Type of Math/Algorithm needed for problem
#2
Re: Type of Math/Algorithm needed for problem
Posted 13 March 2013  09:27 PM
Will multiple of these pirates have the same stats? If so, you might consider using a generating function to help you determine how many possibilities exist for the target. This could also help you find the closest target.
Another possibility is to set up a linear diophantine equation to reach the target. So if pirate1 has a value of 100 and pirate2 has 200, then 100x + 200y = z. Then if gcd(100, 200) divides z, then a solution exists.
Hope this helps some!
Another possibility is to set up a linear diophantine equation to reach the target. So if pirate1 has a value of 100 and pirate2 has 200, then 100x + 200y = z. Then if gcd(100, 200) divides z, then a solution exists.
Hope this helps some!
#3
Re: Type of Math/Algorithm needed for problem
Posted 13 March 2013  09:53 PM
Yes, all pirates have atk, def, int, crg stats, with each having what can be assumed to be random values.
I do not have time to read up on the generating function you have linked too today, I have an assignment to do, but I wanted to keep it in the back of my mind. I'll certainly be spending the next few days on it though when I'm free, I'll let you know if I need help or succeed. Thanks Mac.
I do not have time to read up on the generating function you have linked too today, I have an assignment to do, but I wanted to keep it in the back of my mind. I'll certainly be spending the next few days on it though when I'm free, I'll let you know if I need help or succeed. Thanks Mac.
#4
Re: Type of Math/Algorithm needed for problem
Posted 13 March 2013  09:54 PM
Generating functions are really abstract, if you've never worked with them before. The pairwise GCD approach in the linear Diophantine equation is an easy and good approach, though. Good luck!
#5
Re: Type of Math/Algorithm needed for problem
Posted 13 March 2013  09:59 PM
Well I will have a fair bit of time, So I'll likely start at the fundamentals, I want to learn the math too, not just solve the problem.
Page 1 of 1
