用于查找数字集是否可以加起来为 X 的算法，具有约束直方图

Question

(动机:考虑一个问题，您必须从可用球员中选择一支运动队。每个球员的特定技能水平与他们的薪水期望成正比，并且您希望该技能/薪水水平的总和为完全符合你的总工资帽。)

我需要编写以下函数:

 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 返回真当且仅当一个包含 M 个整数的数组 X 可以被分配给以下三个约束:

1. 所有 i , 0 <= X[i] <= N
2. 所有 v , X 的元素数量具有值(value) v是 <= H[v]
3. X的总和为T

我可以通过什么算法或方法来实现possibleAssign？

Answer 1

这个问题似乎可以从 Subset Sum Problem 中减少，或者更广为人知的变体:knapsack problem , 它们是 NP-Hard，因此没有已知的多项式解。

不过，看起来T够小了，幸运的是，有一个pseudo polynomial solution使用 DP 解决问题。

因为这个问题已经和背包问题很相似，我会尝试将问题简化为适合背包问题，然后调用 DP 算法来寻找背包问题的最佳解决方案:

我首先过滤列表，只保留值为 v 的 H[v] 个元素。现在，按如下方式设置元素:

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

这会让你继续 - 给你最大数量的元素，可以用薪水约束 T 分配