Demo entry 4130017

chaining

   

Submitted by anonymous on Mar 22, 2016 at 15:12
Language: Python 3. Code size: 4.7 kB.

# The definition of the Class Interval will make the program more understandable

class Interval(object):
    def __init__(self, b, e, w):
    
        self.begin = b
        self.end = e
        self.weight = w
        
    def __str__(self):
        string = "Interval: (" + str(self.begin) + ", " + str(self.end) + ") Weight: " + str(self.weight) 
        return string

    def __repr__(self):
        string = "Interval: (" + str(self.begin) + ", " + str(self.end) + ") Weight: " + str(self.weight) 
        return string

    def __lt__(self, other):
        return self.begin <= other.begin
    
    
def best_intervals(intervals):
    """
    Takes a list of Interval objects and finds and prints a collection of disjoint intervals
    with maximum total weight. If there is more than one optimal solution, the function will
    only find one of them. For instance, the algorithm will always reject zero-weighted intervals.
    """

    # We create a dynamic programing table named "score", which stores the values of the function score(i, j).
    
    # We define score(i, j) as the maximum total wight that can be obtained with the restrictions:
    # a) only positions greater or equal than i are considered
    # b) only intervals with a higher or equal index than j can be used (the index of an interval is
    # in the intervals list.

    # For the algorithm to work, we need the intervals to be sorted according to their staring position (begin).
    # Even though the examples provided were already sorted, we apply the sort() function not to make implicit assumptions. 
    
    intervals.sort()

    # We initialize the score table with zero values; the values of the last column will remain zero. 
    score = []
    for i in range(intervals[-1].begin + 1):
        score.append((len(intervals)+1)*[0])

    # The remaining values of score are calculated according to a recursive definition. Thus, the values are
    # calculated from right to left.
    
    # i ranges from 0 to the beginning of the last interval, because for higher values of i score(i, j) will be zero.
    # Therefore, we omit those values from the table.
    
    # j ranges from 0 to the number of intervals (len(intervals)). score(i, len(intervals)) will also be zero because
    # it means that we already run out of intervals to use. 
    
    for j in reversed(range(len(intervals))):
        for i in range(intervals[-1].begin + 1):

            if intervals[j].begin < i: # The j-th interval cannot be used, it starts before i. 
                score[i][j] = score[i][j+1]

            else: # The j-th interval can be used. We have to decide whether it is best to use it or not. 

                # If we use the j-th interval, it will be our last choice, because it spans further right than
                # the beggining of any other existing interval.
                if intervals[j].end > intervals[-1].begin: 
                    score[i][j] = max(score[i][j+1], intervals[j].weight)

                # The most general case
                else:
                    score[i][j] = max(score[i][j+1], intervals[j].weight + score[intervals[j].end][j+1])


    # Once the score table has been filled, we know that the maximum score is in score(0, 0).
    # In order to recover the intervals chosen in the best solution, we need to analyze the
    # choices that have driven us to this solution.
    i = 0
    j = 0
    finish = False
    sol = [] # We will store the indices of the chosen intervals in sol

    while not finish:  # In each iteration we guess the origin of score[i][j]
        if score[i][j] == 0:
            finish = True

        elif score[i][j] == score[i][j+1]:
            j = j+1

        else:
            sol.append(j)
            if intervals[j].end > intervals[-1].begin:
                finish = True
            else:
                j = j+1
                i = intervals[j].end

    print("The solution is: ")
    for i in sol:
        print(intervals[i])

    print("And its total weight is: " + str(score[0][0]))

# Input intervals 1 and 2:

intervals1 = [Interval(1, 5, 4), Interval(3, 9, 3), Interval(4, 10, 3), Interval(7, 13, 6), Interval(10, 17, 10),
     Interval(11, 16, 2), Interval(14, 19, 1), Interval(17, 19, 2)]

intervals2 = [Interval(1, 5, 5), Interval(2, 3, 3), Interval(4, 8, 6), Interval(6, 12, 10), Interval(7, 17, 12),
              Interval(9, 10, 1), Interval(11, 15, 7), Interval(13, 14, 0), Interval(16, 18, 4)]

# We run the function on both interval sets
best_intervals(intervals1)
best_intervals(intervals2)

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).