CODEWITHSUNDEEP
algorithmdynamic-programming
khirod
khirod

Reputation: 345

Need help making team LINEUP by dynamic programming

Imagine you are a football team-coach. There are 11 players and 11 different positions in the field in which players play. Each player is capable of playing at all 11 different positions with a certain rating at the specified position.

You being the coach of the team have to decide the strongest possible LINEUP for the team (consisting of all 11 players) such that overall rating (i.e, sum of ratings) is maximized. No two players can play at the same position.

As an example, consider a smaller LINEUP problem in which only 3 players play a certain game.

3 2 1
4 1 5
6 7 3

Player 1 can play at position 1 with rating 3, at position 2 with rating 2 and at position 3 with rating 1. Similarly for all the players the ith column represents their rating at ith position. The best LINEUP will be when player 1 plays at position 1, player 2 at position 3 and player 3 at position 2, resulting in maximum rating = 15 (3 + 5 + 7).

So, how can this problem be solved by Dynamic Programming? I have read on forums someone solving this problem by DP but I am unable to figure out how the problem possesses Optimal Substructure. So please help me figure out that....

Plz also mention that is it possible or not to solve the problem by DP

And please edit the title appropriately...

Upvotes: 0

Views: 1182

Answers (2)

songlj
songlj

Reputation: 927

it's a matching problem. u can use KM algorithm to solve that wiki and Hungarian Method which Alex mentioned is a special case of KM. for DP method, Ales gave the right answer. since the number of players is not big, a bit manipulation method can be used here

Upvotes: 0

Alexander Chertov
Alexander Chertov

Reputation: 2108

I believe you have an assignment problem here, which can be solved by the Hungarian Method.

And if you really want to have a DP solution, here is one idea. Why not have a F[i,j], i=0..11, j = 0..2^11-1. i - is the number of players you are allowed to select from and j - is a bitmask representing the field positions that are covered and F is the maximum "team value" you can get. For i = 1, for example, only those values of j whose binary representation contains at most one set bit are "valid". Obviously you cannot conver more than one position with just one player.

// initialize the F[][] array with -infinity
F[0][0] = 0;

for(i = 1; i <= 11; ++1)
{
  for(j = 0; j < 2^11; ++j)
    for(k = 0; k < 11; ++k )
    if( (j & (1 << k)) == 0 ) // k-th position is not occupied?
      F[i][j | (1 << k)] = max( F[i][j | (1 << k)], F[i-1][j] + <value of payer i playing at position k> );
}

ANSWER = F[11][2^11-1]

This obviously can be optimized: for F[i] we are only interested in bitmasks containing exactly i set bits.

There was a name for the technique of turning a combinatorial problem into a DP problem by representing the possible states with a bitmap, but I don't remember it. The proper solution for this is still Hungarian method.

Upvotes: 2

Related Questions