mercredi 4 mars 2015

Dynamic Programing approach for a subset sum



Given the following Input



10 4 3 5 5 7


Where



10 = Total Score

4 = 4 players

3 = Score by player 1

5 = Score by player 2

5 = Score by player 3

7 = Score by player 4


I am to print players who's combine score adds to total so output can be 1 4 because player 1 + player 4 score = 3 + 7 -> 10 or output can be 2 3 because player 2 + player 3 score = 5 + 5 -> 10


So it is quite similar to a subset sum problem. I am relatively new to dynamic programing but after getting help on stackoverflow and reading dynamic programing tutorials online and watch few videos online for past 3 days. The following code i have come with so far.



class Test
{
public static void main (String[] args) throws java.lang.Exception
{
int[] test = {3,5,5,7};
getSolution(test,3,10);
}

//pass total score, #of players (size) and the actual scores by each player(arr)
public static int getSolution(int[] arr,int size, int total){


int W = total;
int n = size;
int[][] myArray = new int[W+1][size+1];

for(int i = 0; i<size+1; i++)
{
myArray[i][0] = 1;
}
for(int j =1; j<W+1; j++)
{
myArray[0][j] = 0;
}

for(int i =1; i<size+1; i++)
{
for(int x=1; x<W+1; x++)
{
if(arr[i] < x)
{
myArray[i][x] = myArray[i-1][x];
}
else
{
myArray[i][x] = myArray[i-1][x-arr[i]];
}
}
}

return myArray[n][W];
}

}


For some reason i am not getting expected result. I have been trying to find bug in this issue for past 7+ hours without 0 success. I would highly appreciate it if someone can help fix the issue to get the desired result.


Also please forgive my English it is not my first language.




Aucun commentaire:

Enregistrer un commentaire