[Python知识库]weight interval scheduling

问题描述

在上一篇interval scheduling问题的基础上，工作任务再增加weight属性，要求找出满足工作时间不重叠的工作组合，且组合的权weight为最大。

思路

这道题用动态规划的思路解题。首先将所有工作按照结束时间进行排序。然后还是从最后一个工作开始考虑。
对于每一个工作j，我们有两种情况
1.选择它，那么它以前与它工作时间有重叠的，就要被淘汰掉。直到再次遇到一个没有重叠的，再次进行2选1.
2.不选择它，那么就对它前一个工作继续进行2选1。
我们需要的就是max{选择1，选择2}
而边界条件就是将所有工作找完。

伪代码表示

为了便于表达，我们令opt(j)表示为对前j项工作寻找最优解。p(j)表示为向前寻找最近的与第j项工作时间不重叠的工作。
(1) if j=0 : obt(j) = 0
(2) else : obt(j) = max{obt(j - 1), obt(p(j) + j.weight)

python代码实现

class Job:
    startime = 0
    endtime = 0
    weight = 0


# 由文本文件初始化工作集
def ini_jobs(filename):
    infile = open(filename, "r")
    data = infile.readline()
    i = 0
    jobs = list()
    while data != '':
        jobs.append(Job())
        jobs[i].startime = int(data[0:2].lstrip())
        jobs[i].endtime = int(data[2:5].lstrip())
        jobs[i].weight = int(data[5:8].lstrip())
        i += 1
        data = infile.readline()
    return jobs


# 按照结束时间对工作集进行排序
def sort_by_etime(jobs):
    i = len(jobs)-1
    while i > 0:
        j = 0
        while j < i:
            if jobs[j].endtime > jobs[j+1].endtime:
                tmp = jobs[j]
                jobs[j] = jobs[j + 1]
                jobs[j + 1] = tmp
            j += 1
        i -= 1


# 检查两个工作的时间是否存在重叠
def is_overlap(job1, job2):
    if job1.startime >= job2.endtime or job1.endtime <= job2.startime:
        return False
    else:
        return True


# 检查排序工作集中第j个往前找到的最近的与第J个没有重叠的工作
def filtrate(sorted_jobs, j):
    if j == 0:
        return -1
    else:
        i = j - 1
        while i != -1 and is_overlap(sorted_jobs[j], sorted_jobs[i]):
            i -= 1
        return i


# 动态规划找到不含重叠工作的集合的权重和
def opt(sorted_jobs, j):
    if j == -1:
        return 0
    else:
        return max(opt(sorted_jobs, filtrate(sorted_jobs, j)) + sorted_jobs[j].weight, opt(sorted_jobs, j - 1))


def fun():
    tasks = ini_jobs('test')
    sort_by_etime(tasks)
    res = opt(tasks, len(tasks)-1)
    print(res)


if __name__ == '__main__':
    fun()

test的文件内容形如

 0 10 11
 1  2 13
 3  5 14
 2  3 22
 2  5 43