Algorithm Development, Similar to the Knapsack Problem
I need an algorithm very similar to the Knapsack Problem, but with a twist. I have a list of items each with a value, cost, and class. The knapsack must have at least one of each class and fit under the cost and have no repeats.
For example, I have the following items:
1). Val: 10, Cost: 8, Class: 'A'
2). Val: 11, Cost: 7, Class: 'A'
3). Val: 10, Cost: 8, Class: 'B'
4). Val: 6, Cost: 7, Class: 'C'
Knapsack max: 23
The twist is the Knapsack needs at least one of each class while fitting under the cost limit.
I need this algorithm for a fantasy football website I am creating. I have a decent familiarity with programming, but not with algorithms and this is where I need the help. The premise is basically you have 8 positions (qb, rb, rb, wr, wr, wr, k, def) all of which have many different players. Each player has a projected amount of points (val) and a salary (cost). Your knapsack is a team you must put together within a given salary (knapsack max weight). How do you maximize the knapsack value? Here is an exact sample http://www.head2head.com/football/salarycap/mock/
I would prefer the algorithm to be made with python, but if you can make the case for another with concerns of speed and other reasons, I would be fine with switching.
The most important part of this algorithm is speed. Ideally, I'd like the end product to be able to do calculations within 3 seconds. Also keep in mind that the dataset is completely dynamic, it will be changing on a daily basis.
The input of the algorithm should be the max salary given. (The knapsack max weight)
The output should be like follows, and remember you are trying to maximize knapsack value, while making sure you fulfill each class WITH NO REPEATS:
I have an example dataset attached, it contains player names, positions, projected points, and salaries. Max weight: 106.
If you have any questions feel free to ask.