1

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

我需要编写以下函数：

 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

如果可以使用以下三个约束分配 M 个整数的数组 X，则 possibleAssign 返回 true：

  1. 福拉尔i_0 <= X[i] <= N
  2. Forall ,v的元素个数<= H[v]Xv
  3. X的总和是T

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

4

1 回答 1

3

这个问题似乎可以从子集和问题中减少，或者它是更知名的变体：背包问题，它是 NP-Hard，因此没有已知的多项式解决方案。

然而，T 似乎足够小，幸运的是，有一个使用 DP 的问题的伪多项式解决方案。

因为这个问题已经和背包问题很相似了，所以我会尝试减少问题以适应背包问题，然后调用 DP 算法来找到背包问题的最佳解决方案：

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

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

这将使您继续前进 - 为您提供可以分配工资约束 T 的最大元素数量

于 2012-07-03T12:33:53.090 回答