生成组合的动态规划

Question

我参加了技术 phone 面试，在被问到这个问题之前我的表现还不错。我完全迷路了，我对如何解决这样的问题一无所知。

您将获得以下输入：总得分、玩家人数、每位玩家的得分。示例输入为

10 4 3 5 5 7

在哪里

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

您要打印出等于总分的任意组合。例如，我们知道玩家 4 和玩家 1 的综合得分可以是总分 10。因此上述答案的输出将是

1 4

1 = 玩家 1 的索引 4 = 玩家 4 的索引。是的，我知道玩家 1 的索引在技术上是 0，但他们说这样打印出来。如果没有匹配的组合，您可以打印出 none 或您喜欢的任何内容。那没关系。

我的尝试

好吧，我没有保持沉默，而是首先告诉面试官我可以使用蛮力方法来解决这个问题。他说当然可以，但我们需要更好的运行时间。

所以我开始想我们可以找到所有可能导致总美元的组合，并使用 MEMOIZATION 来存储以前存储的值。我想不出一种生成所有连击的方法，所以我被困在那里。

更新他还提到我可以给你的最高分数是 1000。我什至不知道为什么这很重要？

如果有人能在正确的方向上激励我，甚至提供 pseudo/working java 如何解决此类问题的示例，我将不胜感激。我认为这是一个普遍问题，我真的很想了解如何解决这个问题

Answer 1

这是subset sum problem，假设你的分数是相对较小的整数，它可以用DP在伪多项式时间内解决：

D(i,0) = 1
D(0,x) = 0     x > 0
D(i,x) = D(i-1, x) + D(i-1, x-arr[i])

以上递归公式将生成大小为total_score X num_players的矩阵。可能组合的数量在矩阵的右下角条目中表示。

这个想法是模仿穷举搜索，对于每个人，您可以添加或不添加，然后调用递归来解决更小的问题。

DP解决方案的伪代码：

Input:
let W be the total score
let arr be the array of players scores
let n be the size of arr
Pseudo Code:
declare 2d array D of size W+1 X n+1
//initialization of "borders":
for each i from 0 to n+1:
    D[i][0] = 1
for each x from 1 to W+1
    D[0][x] = 0
//the DP:
for each i from 1 to n+1:
   for each x from 1 to W+1:
       if arr[i] < x:
          D[i][x] = D[i-1][x]
       else:
          D[i][x] = D[i-1][x] + D[i-1][x-arr[i]]
//by here you have the matrix D filled up
//the wanted value is D[n][W]
return D[n][W]

生成组合的动态规划

Dynamic Programing to generate combinations

java

algorithm

recursion

dynamic-programming