最低工资问题
Minimum salary proglem
我们有n个学生。对于第 i 个学生,我们知道它的数学 (mi) 和编码技能 (ci)。我们希望每个学生都有一位老师。但是,只有当学生在数学和编码方面具有相同或更好的技能时,教师才能教学生。每个老师可以教尽可能多的学生。
数学技能为 M、编码技能为 C 的老师获得 C * M 的薪水。问题是最小化所有教师的整体工资。
示例:
4
1 6
4 2
2 2
2 5
输出:20。
因为我们可以得到(2, 6)和(4,2),所以我们需要付出2*6 + 4*2 = 20
我发现最简单的方法就是暴力破解 c 和 m 的所有可能值(有一些限制)并最小化 c * m。但是这个问题属于动态规划部分。那么任何人都可以提供任何想法如何更有效地解决它吗?
第一步,清理数据:
- 删除被支配的学生。 (如果 c_x >= c_y 且 m_x >= m_y,则 x 支配 y)
- 按 c_i 排序。所以我们有 c_1 < c_2 ... < c_n,不难推断 m_1 > m_2 ... > m_n (
theorem 1
)
第2步,计算:
f(i) = the minimal salary for teaching student 1..i
在此之前,我们定义:
s(i,j) = the salary of employing only one teacher to teaching student i..j(i < j)
s(i,j) = max(c_(i..j)) * max(m_(i..j))
s(i,j) = c_j * m_i (by theorem 1)
所以我们可以得到:
f(i) = min(f(j) + s(j+1,i)) j >= 1 and j < i
通过简单的实现,我们可以在 O(n^2) 中计算出 f(n)
(答案)。
有任何问题都可以在这里提问,我会尽快回复。
我们有n个学生。对于第 i 个学生,我们知道它的数学 (mi) 和编码技能 (ci)。我们希望每个学生都有一位老师。但是,只有当学生在数学和编码方面具有相同或更好的技能时,教师才能教学生。每个老师可以教尽可能多的学生。
数学技能为 M、编码技能为 C 的老师获得 C * M 的薪水。问题是最小化所有教师的整体工资。
示例:
4
1 6
4 2
2 2
2 5
输出:20。
因为我们可以得到(2, 6)和(4,2),所以我们需要付出2*6 + 4*2 = 20
我发现最简单的方法就是暴力破解 c 和 m 的所有可能值(有一些限制)并最小化 c * m。但是这个问题属于动态规划部分。那么任何人都可以提供任何想法如何更有效地解决它吗?
第一步,清理数据:
- 删除被支配的学生。 (如果 c_x >= c_y 且 m_x >= m_y,则 x 支配 y)
- 按 c_i 排序。所以我们有 c_1 < c_2 ... < c_n,不难推断 m_1 > m_2 ... > m_n (
theorem 1
)
第2步,计算:
f(i) = the minimal salary for teaching student 1..i
在此之前,我们定义:
s(i,j) = the salary of employing only one teacher to teaching student i..j(i < j)
s(i,j) = max(c_(i..j)) * max(m_(i..j))
s(i,j) = c_j * m_i (by theorem 1)
所以我们可以得到:
f(i) = min(f(j) + s(j+1,i)) j >= 1 and j < i
通过简单的实现,我们可以在 O(n^2) 中计算出 f(n)
(答案)。
有任何问题都可以在这里提问,我会尽快回复。