your algorithm is wrong

Attach correct solution

Assuming that you are following this pdf: http://www.cs.princeton.edu/~wayne/cs423/lectures/dynamic-programming-4up.pdf, I am using the same example as Slide-4, but with different weight settings.

For the toy data, the best schedule should be selecting 5th, 8th job.

Your implementation and algorithm is nothing but greedy algorithm.

#!/usr/bin/env python

# wrong algorithm:
# http://www.cs.princeton.edu/~wayne/cs423/lectures/dynamic-programming-4up.pdf
#

import numpy as np
NEGINF = -np.inf
#==== prepare data ====
# 1-based
n = 8
idx = range(1, n+1)
tm_b = [NEGINF, 1, 3, 0, 4, 3, 5, 6, 8] # begin time
tm_f = [NEGINF, 4, 5, 6, 7, 8, 9, 10, 11] # finish time
# val = [(x+1) for x in np.arange(n+1)]
# np.random.shuffle(val)
val = [NEGINF, 1, 1, 1, 1, 100, 1, 1, 1]

print tm_b
print tm_f
print val
#
#==== perform dynamic programming ====
#
opt_val = [NEGINF] * (n+1)
opt_val = [opt_val] * (n+1+1)
opt_val = np.matrix(opt_val)
plan = np.matrix(opt_val)
#==== compute list q ====
q = [-1, 0, 0, 0, 1, 0, 2, 3, 5]
p = [-1, 4, 6, 7, 8, 8, -1, -1, -1]
#==== bottom-up

for i in xrange(1, n +1+1):
    opt_val[i, i-1] = 0 
    plan[i, i-1] = 0

for i in xrange(1, n +1):
    plan[i, i] = i

for l in xrange(1, n +1):
# for l in xrange(1, 6):
    # print "\n== " + str(l)
    for i in xrange(1, (n - l + 1 +1)):
        j = i + l - 1
        opt_val[i, j] = NEGINF
        for r in xrange(i, j +1):
            # compatible
            lft_most_idx = r - 1
            rit_most_idx = r + 1
            while lft_most_idx >= i and tm_f[lft_most_idx] >= tm_b[r]:
                lft_most_idx = lft_most_idx - 1
            while rit_most_idx <= j and tm_b[rit_most_idx] <= tm_f[r]:
                rit_most_idx = rit_most_idx + 1
            tmp = val[r] + opt_val[i, lft_most_idx] + opt_val[rit_most_idx, j]
            # if i == 1 and j == 2:
                # print map(str, [r, lft_most_idx, rit_most_idx, tmp, opt_val[i, j]])
            if opt_val[i, j] < tmp:
                opt_val[i, j] = tmp
                plan[i, j] = r
    # print opt_val
print plan
print opt_val

##==== print best
def renderPlan(plan, q, p, n):
    r = int(plan[1, n])
    renderPlanSub(1, q[r], plan, q, p)
    print r
    renderPlanSub(p[r], n, plan, q, p)

def renderPlanSub(i, j, plan, q, p):
    if i >=0 and j >= 0 and i <= j:
        t = int(plan[i, j])
        renderPlanSub(i, q[t], plan, q, p)
        print t
        renderPlanSub(p[t], j, plan, q, p)

CarterZhou / algorithms_practice

your algorithm is wrong #1