Dynamic Programing to solve subset of given sum

Question

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

Output should print the index of players who's score equal to 10. So for given above output it should print 1 4 or 2 3 because player 1 + player 4 score adds up to 10 and so does the scores by player 2 and player 3. I do not need to PRINT BOTH or ALL combinations. I just want to print any one combination that works.

For INPUT : 8 3 2 2 4 OUPUT : 1 2 3 since scores of player 1 player 2 and player 3 equal the total score of 8

So i have been reading Dynamic programing tutorials and videos for past week and also got help on stack overflow to fix my initial code.

Following is what i have so far

    public boolean findSolution(int[] scores, int total) {
    int W = total;
    int players = scores.length;

    boolean[][] myArray = new boolean[players + 1][total + 1];

    for (int player = 0; player <= players; player++) {
        myArray[player][0] = true;
    }
    for (int score = 1; score < total; score++) {
        myArray[0][score] = false;
    }
    for (int player = 1; player <= players; player++) {
        for (int score = 1; score <= total; score++) {
            myArray[player][score] = myArray[player - 1][score];
            if (score >= scores[player - 1]) {
                myArray[player][score] = myArray[player - 1][score
                        - scores[player - 1]]
                        || myArray[player][score];
            }
        }
    }
    return myArray[players][W];

}

This logic creates 2d array and does exhaustive search to see if the combination for a given total is possible and will return true if it is and false if it is not. Now i am having trouble printing the indexes of the players that make it true. So would highly appreciate if someone can help me print the index of a set of players who's score equals the total. I dont NEED TO PRINT all combinations.

Also please ask any question if you don't understand as i am not native English speaker.

possible duplicate of [Dynamic Programing approach for a subset sum](http://stackoverflow.com/questions/28867558/dynamic-programing-approach-for-a-subset-sum) — erip, Mar 05 '15 at 21:26
@erip yes duplicate but question is slightly different i am stuck on different part now if that makes sense. sorry otherwise — user1010101, Mar 05 '15 at 21:34

Pham Trung · Accepted Answer · 2015-03-06T08:03:47.227

Ok, so after you have created and updated boolean array myArray.

We will iterate from the last player to the first player, checking if we can use the current player in our final result

int currentScore = total;//Maintain the current score.
for(int i = lastPlayer ; i >= 0; i--){

}

Inside the for loop, to check if this current i player is belong to our final set of player, we need to check if there exists a solution for currentScore - score of i player

if (currentScore >= scores[i] && (i == 0 || myArray[i - 1][currentScore - scores[i]]) {
      //Update current score      
      currentScore -= scores[i];
      //Print name of the player.
      System.out.println("Player " + i);              
}

Dynamic Programing to solve subset of given sum

1 Answers1