algorithm - 查找带有受限直方图的数字集是否可以总计X的算法

（动机：考虑一个问题，你必须从现有球员中选择一支运动队每个球员都有一个与他们的工资期望完全成比例的技能等级，你希望这个技能/工资等级的总和与你的工资上限完全匹配。）
我需要编写以下函数：

 bool possibleAssignment(int N, int M, int T, vector<int> H);

输入约束为：
0 < N <= 50
0 < M <= 50
0 < T <= 2500
H.size() == N + 1
对于所有i，0 <= H[i] <= M
possibleassign返回true如果可以使用以下三个约束为m个int的数组x赋值：
对于所有i，0 <= X[i] <= N
对于所有v，具有X值的v元素的数目是x的和是t
我可以用什么算法或方法实现可能的签名？

最佳答案

这个问题似乎可以从Subset Sum Problem中还原，或者它是已知的变量：knapsack problem，这是NP难的，因此没有已知的多项式解。
然而，它似乎不够小，幸运的是，使用dp有一个pseudo polynomial solution的问题。
因为这个问题和背包问题已经很相似了，所以我试着把这个问题简化成背包问题，然后调用dp算法来寻找背包问题的最佳解：
我先过滤列表，只保留值为v的H[v]元素。现在，按如下所示设置元素：

value(x) = 1
weight(x) = x
Bag size = T

这将使您能够给您提供可以用工资约束T分配的最大数量的元素。