문인철 교수님의 ‘데이터 구조 및 분석: Linear Structure and Dynamic Programming’ 수업
Assembly Line Scheduling in Recursion and DP
DP 코드
# Assembly Line Scheduling in DP
class AssebmlyLinesInDP:
time_station = [[7,9,3,4,8,4],
[8,5,6,4,5,7]]
time_belt = [[2,2,3,1,3,4,3],
[4,2,1,2,2,1,2]]
# set up a memoization table
time_scheduling = [list(range(6)), list(range(6))]
station_tracing = [list(range(6)), list(range(6))]
def strat_scheduling_in_dp(self):
num_station = len(self.time_station[0])
self.time_scheduling[0][0] = self.time_station[0][0] + self.time_belt[0][0]
self.time_scheduling[1][0] = self.time_station[1][0] + self.time_belt[1][0]
for i in range(1, num_station):
if self.time_scheduling[0][i-1] > self.time_scheduling[1][i-1] + self.time_belt[1][i]:
self.time_scheduling[0][i] = self.time_station[0][i] + self.time_scheduling[1][i-1] + self.time_belt[1][i]
self.station_tracing[0][i] = 1
else:
self.time_scheduling[0][i] = self.time_station[0][i] + self.time_scheduling[0][i-1]
self.station_tracing[0][i] = 0
if self.time_scheduling[1][i-1] > self.time_scheduling[0][i-1] + self.time_belt[0][i]:
self.time_scheduling[1][i] = self.time_station[1][i] + self.time_scheduling[0][i-1] + self.time_belt[0][i]
self.station_tracing[1][i] = 0
else:
self.time_scheduling[1][i] = self.time_station[1][i] + self.time_scheduling[1][i-1]
self.station_tracing[1][i] = 1
count_line1 = self.time_scheduling[0][num_station-1] + self.time_belt[0][num_station]
count_line2 = self.time_scheduling[1][num_station-1] + self.time_belt[1][num_station]
if count_line1 > count_line2:
return count_line2, 1
else:
return count_line1, 0
def print_tracing(self, line_tracing):
num_station = len(self.time_station[0])
print(f"line: {line_tracing}, station: {num_station}")
for i in range(num_station-1, 0, -1):
line_tracing = self.station_tracing[line_tracing][i]
print(f"line: {line_tracing}, station: {i}")
lines = AssebmlyLinesInDP()
time, line_tracing = lines.strat_scheduling_in_dp()
lines.print_tracing(line_tracing)
실행결과
lines = AssebmlyLinesInDP()
time, line_tracing = lines.strat_scheduling_in_dp()
lines.print_tracing(line_tracing)
print(time)
line: 0, station: 6
line: 1, station: 5
line: 1, station: 4
line: 0, station: 3
line: 1, station: 2
line: 0, station: 1
38