java - 生成组合的动态规划

Question

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

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

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。我什至不确定为什么这很重要？

如果有人能使我朝着正确的方向前进，或者甚至提供伪/工作 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]