assembly_line_sol.rb

# **PROBLEM STATEMENT**
# Assembly line scheduling w/ 2 lines.

# **OPTIMAL SUBSTRUCTURE**
# Claim: A candidate solution is a finite sequence of entries of A
# and the last element in S is either A[0][n-1] or A[1][n-1].
# If S is the opt. solution for A, then S' = S[:-1] is optimal to
# the subproblem with force S[-1].

# **RECURRENCE RELATION**
# S[0][0] = a[0][0] + E[0]
# S[1][0] = a[1][0] + E[1]
# S[0][j] = min{ s[0][j-1], s[1][j-1]+T[1][j-1] } + A[0][j]
# S[1][j] = min{ s[1][j-1], s[0][j-1]+T[0][j-1] } + A[1][j]

def assembly_line_dp_const_space a, t
  n = a[0].length
  curr1 = a[0][0] + E[0]
  curr2 = a[1][0] + E[1]

  for j in 1..n-1
    prev1 = curr1
    prev2 = curr2
    curr1 = [ curr1, prev2+T[1][j-1] ].min + a[0][j]
    curr2 = [ curr2, prev1+T[0][j-1] ].min + a[1][j]
  end

  return [ curr1+X[0], curr2+X[1] ].min
end

def assembly_line_dp a, t
  n = a[0].length
  s = Array.new(2) {Array.new(n) {0}}
  s[0][0] = a[0][0] + E[0]
  s[1][0] = a[1][0] + E[1]

  for j in 1..n-1
    s[0][j] = [ s[0][j-1], s[1][j-1]+T[1][j-1] ].min + a[0][j]
    s[1][j] = [ s[1][j-1], s[0][j-1]+T[0][j-1] ].min + a[1][j]
  end

  return [ s[0][n-1]+X[0], s[1][n-1]+X[1] ].min
end

A =
[
 [7, 9, 3, 4, 8],
 [8, 5, 6, 4, 5]
]
T = [ [2, 3, 1, 3], [2, 1, 2, 2] ]
E = [2, 4]
X = [3, 6]

puts assembly_line_dp_const_space A, T