# Help Understanding the Type and Complexity of my Programming Task [closed]

I'm working on a programming task that I, without good evidence, have a sneaking suspicion is NP-Complete. With that said, I would like confirmation on this if possible, as well as some suggestion for a way to approximate a reasonable solution. Lastly, if this problem is just some popular problem in disguise, I'd love to look more into that problem. I'll now describe my task.

I am attempting to design a program to optimize daily fantasy baseball rosters given certain information. The context here is that I will be designing rosters of players from various games that consists of 2 pitchers and one player that plays each other position. This is complicated by the fact that each player is assigned a salary relative to their perceived ability and there is an overall cap on how much salary can be used in total. This means I am dealing with restrictions in terms of making sure that I do not exceed the combined salary cap, while also making sure that I have players at each position. To complicate things further, I want to be able to pick a few players (1-5 or so) at each position as my favorites, and have control over what % of my teams they appear in. That is, if I make 50 teams, I'd like to be able to make it so that I can generate these teams by inputting a list like: Player X (pitcher) 5%, Player Y (First Base) 50%, and so on.

Is there any practical way I can solve (approximate fairly accurately) this problem? The overall salary limit seems to make this a tricky problem.

Thanks a lot!

• Welcome to Computer Science Stack Exchange. Please include all relevant information about the composition of a baseball team. Contrary to popular belief, there are countries outside the North American continent, inhabited by people who do computer science, but do not practice baseball, and some of them even participate in stackexchange.com. – babou Jul 16 '15 at 8:12
• What have you tried and where did you get stuck? Our reference questions may be a good starter. – Raphael Jul 16 '15 at 8:22
• I find it unclear. You are describing an optimization problem, but it's not clear what objective function you are trying to optimize. You tell us what restrictions you need to abide by, but not what metric you want to maximize/minimize. Your question is not answerable without this information. Is there some notion of how good each player is? What should the output look like, and can you specify a metric that determines how "good" a particular output is? Are there some restrictions on which players can be assigned to which teams? – D.W. Jul 17 '15 at 1:11
• babou, you are absolutely right that I should have done a better job explaining the rules of baseball. Suffice it to say that the team you construct for fantasy purposes has the following positions: two pitcher slots, slots for 1b, 2b, 3b, ss, catcher, as well as three outfield (of) slots. – Sykology Jul 17 '15 at 10:05
• D.W., your point is also well taken. The main issue is that I'm not necessarily trying to optimize anything. There is a lot of variance in baseball so, while it's possible and common for people to make projections, the truth is that one needs to hone in on a number of players with a good chance of performing well and then create teams where you mix and match all these players. Thus, I am fully happy to generate a bunch of teams that are not optimal based on any projection system, provided that I can control what percentage of my teams a certain player is in based on my expectations of them. – Sykology Jul 17 '15 at 10:07

Divide this problem into two parts.

I am attempting to design a program to optimize daily fantasy baseball rosters given certain information. The context here is that I will be designing rosters of players from various games that consists of 2 pitchers and one player that plays each other position. This is complicated by the fact that each player is assigned a salary relative to their perceived ability and there is an overall cap on how much salary can be used in total. This means I am dealing with restrictions in terms of making sure that I do not exceed the combined salary cap, while also making sure that I have players at each position.

This sounds like the 0-1 Knapsack problem where you have an overall salary cap and salary and importance of each player.

So from a list of all the players available in the market, form your personal roster using this concept.

Now coming to the second part of your question,

I want to be able to pick a few players (1-5 or so) at each position as my favorites, and have control over what % of my teams they appear in. That is, if I make 50 teams, I'd like to be able to make it so that I can generate these teams by inputting a list like: Player X (pitcher) 5%, Player Y (First Base) 50%, and so on.

You have a personal roster at hand and each player has a percentage attached to him. Try a greedy strategy to distribute players.

Pardon my ignorance of baseball's rules but here is a simple example to help you out. Suppose you have 10 teams where each team has to have only one keeper (the guy who stands behind the players with the bats). You have to distribute Keeper X, Y and Z among the two teams. X has a 10% percentage chance, Y has a 90% chance, Z has a 10% chance. So sort the players according in ascending order according to weightage and put X in team 1, Y in team 2 and Z in teams 3 through 10. Similarly sort according to your criteria, and develop your own heuristic to fill each position.