004.py

# 带有限期和效益的单位时间的作业排序贪心算法

import random

def js(D, J, n):
    """
    数组D存放n个作业的期限值，这些存放在数组中的作业是按照它们产生的效益值非递增排序过的；
    数组J存放纳入成为可行解的作业
    n作表总共作业的数量
    k作表已经处理放入J中的作业数量
    i指示当前正在处理的作业
    r表示扫描数组J时的当前扫描位置
    """
    D[0] = J[0] = 0    # 引入虚构作业0，是为了便于处理将作业插入位置1
    k = 1; J[1] = 1    # 初始化时，把第1个作业放入J中，则当前已经处理放入J中的作业数量k为1
    for i in range(2, n+1):   # 第1个作业已经处理了，因此需要处理的作业是第2个到第n个
        r = k                  # 从已经纳入J中的最后一个位置k的作业开始往前扫描
        while D[J[r]] > D[i] and D[J[r]] != r:    # while循环判断寻找当前处理的作业i适合的插入位置
            r -= 1
        if D[J[r]] <= D[i] and D[i] > r:  # 判断如果作业放在位置r后一个位置是否能够在期限值规定内完成
            for m in range(k, r, -1):   # 用for循环把从位置r+1到位置k上的作业都往后移动一个位置
                J[m+1] = J[m]              # 把r+1的位置空出来存放作业i
            J[r+1] = i; k += 1
    return k                              # 返回总个数

if __name__ == '__main__':
    i = 0
    while i < 3:
        # 数组D存放n个作业的期限值，这些存放在数组中的作业是按照它们产生的效益值非递增排序过的
        # 数组J存放纳入成为可行解的作业
        P = [0, 20, 8, 7, 6, 5, 3]   # 效益
        P = random.sample(range(1, 20), 7); P[0] = 0  # 效益
        D = [0, 4, 3, 1, 2, 2, 1]    # 期限值
        D = random.sample(range(1, 8), 7); D[0] = 0   # 期限值
        J = [0, 0, 0, 0, 0, 0, 0]    # 可行解的作业
        n = 6

        k = js(D, J, n)
        print('效益：', P[1: n+2])
        print('期限值：', D[1:n+2])
        print('最优解：', J[1:k+1], '最优解的效益：', sum([P[i] for i in J[1:k+1]]), end='\n\n')

        i += 1  # 计数器