alg3.py

import time
from random import randint

## Pre protocol ##

# n is the only variable in the program that needs touching, everything else is
# randomized!
n = 5             # Increase for more jobs!!!
dm = 0
jobs = []

# Generate random jobs and sort them in deadline order.
for i in range(0, n):
    size = randint(1,10)
    value = randint(1,10)
    deadline = size + randint(1,5)
    rand_job = (size, value, deadline)
    jobs.append(rand_job)

jobs.sort(key=lambda tup: tup[2])

# Find the maximum deadline.
for i in jobs:
    if i[2] > dm:
        dm = i[2]

# Create the matrix that will be used to store the calculations.
matrix = [[0 for x in range(n+1)] for y in range(dm+1)]

# The actual function!
def OPT(n, T):
    for t in range(1,T+1):
        for i in range(1,n+1):
            si = jobs[i-1][0]
            vi = jobs[i-1][1]
            di = jobs[i-1][2]
            matrix[t][i] = max(matrix[t][i-1], (vi + matrix[min(t, di)-si][i-1]) if t >= si else 0)

def backtrace(a, i, T):
    result = []
    while(True):
        if a[T][i] == a[T][i-1]:
            i = i-1
        else:
            result.append(i)
            T = T - jobs[i-1][0]
            i = i - 1
        if i == 0:
            return(result)


############ MAIN ###################
start = time.time()
OPT(n, dm)
end = time.time()
print("List of jobs on the form (si, vi, di):")
print(jobs)
print()
print("Solution given by a bottom up implementation.")
print('\n'.join([''.join(['{:4}'.format(item) for item in row]) for row in matrix]))
print()
print("The maximum value of all jobs is: " + str(matrix[dm][n]))
print("The jobs to be done are: " + str(sorted(backtrace(matrix, n, dm))))
print("Running time: " + str(end-start))

Nästan en pretty print av en matris:

matrix1 = [[i] + row for (i, row) in enumerate(matrix)]
print(''.join(['{:4}'.format(i) for (i, _) in enumerate(matrix[0])])
print('\n'.join([''.join(['{:4}'.format(item) for item in row]) for row in matrix1]))