python代码用分治法解决写作业问题 小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。
时间: 2024-03-03 13:50:33 浏览: 12
好的,根据您提供的问题,可以使用分治法解决写作业问题。
分治法是一种递归的思想,将问题分解成更小的子问题,然后将子问题的解合并起来得到原问题的解。
对于这个问题,我们可以将其分解成更小的子问题,然后合并得到最优解。
具体来说,我们可以按照作业截止时间的先后顺序,将作业分为两组,一组是截止时间在中间之前的作业,另一组是截止时间在中间之后的作业。然后分别递归求解两组作业的最优解,再将两组作业的最优解合并起来得到整个问题的最优解。
以下是使用 Python 代码实现分治法解决写作业问题的示例:
```python
def min_penalty(n, t, k):
if n == 0:
return 0
if n == 1:
return k[0] if t[0] < 1 else 0
mid = n // 2
left_t = t[:mid]
left_k = k[:mid]
right_t = t[mid:]
right_k = k[mid:]
left_pen = min_penalty(len(left_t), left_t, left_k)
right_pen = min_penalty(len(right_t), right_t, right_k)
t_pen = []
for i in range(mid):
if t[i] >= mid:
t_pen.append(k[i])
t_pen.sort(reverse=True)
for i in range(len(t_pen)):
if i >= mid:
break
left_pen += t_pen[i]
return left_pen + right_pen
```
这个函数的输入参数包括作业的数量n,每个作业的截止时间t,以及每个作业逾期的扣分k。返回值是最少需要扣的分数。
函数首先检查作业数量是否为0或1,如果是则直接返回对应的扣分。否则,将作业分为两组,分别递归求解两组作业的最优解。然后将中间的作业按照截止时间顺序排序,计算需要扣的分数,并将其加到左边的作业的扣分中。最后将左边和右边的扣分加起来,返回最终的扣分。
可以调用这个函数来解决您提供的样例问题:
```python
n = 3
t = [1, 3, 1]
k = [6, 2, 3]
min_penalty(n, t, k)
```
输出结果为4,表示最少需要扣除4分。