求解给定总和子集的动态规划

Question

给定以下输入

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

输出应该打印得分等于 10 的玩家的索引。所以对于上面给出的输出，它应该打印 1 4 或 2 3 因为玩家 1 + 玩家 4 的分数加起来是 10，所以玩家 2 的分数也是和玩家 3。我不需要同时打印或打印所有组合。我只想打印任何一种有效的组合。

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

所以我过去一周一直在阅读动态编程教程和视频，并且还获得了有关堆栈溢出的帮助来修复我的初始代码。

以下是我到目前为止的内容

    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];

}

此逻辑创建二维数组并进行详尽搜索以查看给定总数的组合是否可能，如果是则 return 为真，否则为假。现在我无法打印使它成为现实的玩家索引。因此，如果有人可以帮助我打印一组得分等于总分的球员的索引，我将不胜感激。我不需要打印所有组合。

另外，如果您不明白任何问题，因为我不是英语母语者。

Answer 1

好的，在您创建并更新布尔数组后 myArray。

我们将从最后一个玩家迭代到第一个玩家，检查我们是否可以在最终结果中使用当前玩家

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

}

在 for 循环中，为了检查当前 i 玩家是否属于我们的最终玩家集合，我们需要检查是否存在 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

java

algorithm

dynamic-programming