5 dimensionnal knapsack problem

[shooter27]

Hi, 

 

So I'm in university and right now I have to do an algorithm to solve a problem using dynamic programming. My teacher showed us the knapsack problem for two dimensional arrays and gave us our problem to solve. 

I cant send it since its in french, but basically I have to find the best possible team from a list of hockey players by maximizing their expected points (the value) and where their weight are their salaries. 
Now, that not complicated at all but I also have to take into consideration that the team needs a certain number of attack, defense and goalkeepers players. Hence why I now have 5 dimensions. down below is the code I have right now. It does not work. How would you go about solving this problem?

int i, j, k, l, m;
	int nbGardiens, nbDefenseurs, nbAttaquants = 0;
	int K[joueurs.size()+1][budget+1][nb_gardiens+1][nb_defenseurs+1][nb_attaquants+1];
	for (i = 0; i <= joueurs.size(); i++)
	{
		for (j = 0; j <= budget; j++)
		{
			for (k = 0; k <= nb_gardiens; k++)
			{
				for (l = 0; l <= nb_defenseurs; l++)
				{
					for (m = 0; m <= nb_attaquants; m++)
					{
						if(i == 0 || j == 0){
							K[i][j][k][l][m] = 0;
						}
						else if (joueurs.at(i-1).salaire() <= j)
						{	
							unsigned int position = joueurs.at(i-1).position();
							if(position == Joueur::GARDIEN && nbGardiens < nb_gardiens){
								K[i][j][k][l][m] = max(joueurs.at(i-1).points() + K[i-1][j-joueurs.at(i-1).salaire()][k][l][m],  K[i-1][j][k][l][m]); 
								nbGardiens++;
							}
							else if (position == Joueur::GARDIEN)
							{
							 	K[i][j][k][l][m] = max(joueurs.at(i-1).points() + K[i-1][j-joueurs.at(i-1).salaire()][k-1][l][m],  K[i-1][j][k][l][m]);
							}
							if (position == Joueur::DEFENSEUR && nbDefenseurs < nb_defenseurs)
							{
								K[i][j][k][l][m] = max(joueurs.at(i-1).points() + K[i-1][j-joueurs.at(i-1).salaire()][k][l][m],  K[i-1][j][k][l][m]);
								nbDefenseurs++;
							}
							else if (position == Joueur::DEFENSEUR)
							{
								K[i][j][k][l][m] = max(joueurs.at(i-1).points() + K[i-1][j-joueurs.at(i-1).salaire()][k][l-1][m],  K[i-1][j][k][l][m]);
							}
							if (position == Joueur::ATTAQUANT && nbAttaquants < nb_attaquants)
							{
								K[i][j][k][l][m] = max(joueurs.at(i-1).points() + K[i-1][j-joueurs.at(i-1).salaire()][k][l][m],  K[i-1][j][k][l][m]);
								nbAttaquants++; 
							}else if (position == Joueur::ATTAQUANT)
							{
								K[i][j][k][l][m] = max(joueurs.at(i-1).points() + K[i-1][j-joueurs.at(i-1).salaire()][k][l][m-1],  K[i-1][j][k][l][m]);
							}
							
						}else
						{
							K[i][j][k][l][m] = K[i-1][j][k][l][m];
						}
					}
					
				}
				
			}
		}
	}

 

[Franck]

You are doing a first fit i guess, not a full bin-packing algorithm right ?

 

If it's a first fit you don't need a 5d knapsack. What i would do is a bin packing with the minimum required of players by positions with a standard 2d knapsack.

So you run three 2d knapsack, one for each position and that gave you sack of 2 goalies, 3 offence, 2 defence.

 

Now you run a fourth knapsack that pack all 1 of each group into teams once. Let's say you have 10 teams

then you end up with 10 bin with 1 bin of goalies, 1 bin of offence and 1 bin of defence each. so each team has the minimum

amount of players.

 

Finally the last step is to take every leftover players and use the knapsacks of the "team" that just have the minimum in them and continue filling them until full.

 

 

[frankussd]

I would be interested to know the progress you made for this problem. I got the exact same task to do and for now the closest thing I can find is the MCKP but the exactly 1 object per class is problematic.