Dynamic programming algorithms - 2

dynamicProgrammingAlgorithms2.py

'''Course: https://www.coursera.org/learn/algorithmic-toolbox#about'''


def knapsackWithRepetitions(maxCapacity, weightsList, valuesList):
    '''returns optimal solution. Maximize total value of items that can fit.
    Knapsack can contain more than 1 quantity of each item'''

    knapsackValList = [None] * (maxCapacity+1)
    knapsackValList[0] = 0

    for weight in range(1, maxCapacity+1):
        knapsackValList[weight] = 0

        for item in range(len(weightsList)):
            if weightsList[item] <= weight:
                value = knapsackValList[weight - weightsList[item]] + valuesList[item]

                if value > knapsackValList[weight]:
                    knapsackValList[weight] = value

    return knapsackValList[maxCapacity]




def knapsackWithoutRepetitions(maxCapacity, weightsList, valuesList):
    '''returns optimal solution. Maximize total value of items that can fit.
    Knapsack can ONLY contain 1 quantity of each item'''

    numOfItems = len(weightsList)
    knapsackValList = []
    for item in range(numOfItems+1):
        knapsackValList.append([None] * (maxCapacity+1))

    for item in range(numOfItems+1):
        knapsackValList[item][0] = 0
    for weight in range(maxCapacity+1):
        knapsackValList[0][weight] = 0


    for item in range(1, numOfItems+1):
        for weight in range(1, maxCapacity+1):

            knapsackValList[item][weight] = knapsackValList[item-1][weight]

            if weightsList[item-1] <= weight:
                value = knapsackValList[item-1][weight-weightsList[item-1]] + valuesList[item-1]

                if value > knapsackValList[item][weight]:
                    knapsackValList[item][weight] = value

    return knapsackValList[numOfItems][maxCapacity]





def knapsackWithRepetitionsRecursive(maxCapacity, weightsList, valuesList, maxValueDict):
    '''Recursive approach. Using dictionary to store solution so that it doesn't recompute.
    This technique is called Memoization.
    If all sub-problems must be solved, iterative approaches above are faster as there is no recursion overhead.
    This approach is faster if, for example all the weights, and maxCapacity are multiples of 100'''

    if maxCapacity in maxValueDict:
        return maxValueDict[maxCapacity]

    maxValue = 0
    for item in range(len(weightsList)):
        if weightsList[item] <= maxCapacity:

            value = knapsackWithRepetitionsRecursive(maxCapacity - weightsList[item], weightsList, valuesList, maxValueDict) + valuesList[item]

            if value > maxValue:
                maxValue = value

    maxValueDict[maxCapacity] = maxValue
    return maxValue




def minMax(index1, index2, operationList, minValList, maxValList):
    '''used in parentheses function below.
    Calculates the minimum and maximum between 2 sub expressions'''

    minVal = 1e+5
    maxVal = -1e+5

    for index in range(index1, index2):

        if operationList[index] == '+':
            subExprA = maxValList[index1][index] + maxValList[index+1][index2]
            subExprB = maxValList[index1][index] + minValList[index+1][index2]
            subExprC = minValList[index1][index] + maxValList[index+1][index2]
            subExprD = minValList[index1][index] + minValList[index+1][index2]
        elif operationList[index] == "-":
            subExprA = maxValList[index1][index] - maxValList[index+1][index2]
            subExprB = maxValList[index1][index] - minValList[index+1][index2]
            subExprC = minValList[index1][index] - maxValList[index+1][index2]
            subExprD = minValList[index1][index] - minValList[index+1][index2]
        elif operationList[index] == '*':
            subExprA = maxValList[index1][index] * maxValList[index+1][index2]
            subExprB = maxValList[index1][index] * minValList[index+1][index2]
            subExprC = minValList[index1][index] * maxValList[index+1][index2]
            subExprD = minValList[index1][index] * minValList[index+1][index2]
        elif operationList[index] == '/':
            subExprA = maxValList[index1][index] / maxValList[index+1][index2]
            subExprB = maxValList[index1][index] / minValList[index+1][index2]
            subExprC = minValList[index1][index] / maxValList[index+1][index2]
            subExprD = minValList[index1][index] / minValList[index+1][index2]
        else:
            raise Exception("Operations allowed: +, -, *, /")

        minimum = min(subExprA, subExprB, subExprC, subExprD)
        if minimum < minVal:
            minVal = minimum
        maximum = max(subExprA, subExprB, subExprC, subExprD)
        if maximum > maxVal:
            maxVal = maximum

    return minVal, maxVal




def parentheses(numbersList, operatorsList):
    '''returns optimal solution.
    Maximize the value of the expression by placing parentheses anywhere in the expression'''

    lengthOfNumList = len(numbersList)

    if lengthOfNumList - len(operatorsList) != 1:
        raise Exception("length of operatorsList should be length of numbersList - 1")

    maxValList = []
    minValList = []

    for num in range(lengthOfNumList):
        minValList.append([None] * lengthOfNumList)
        maxValList.append([None] * lengthOfNumList)

    for num in range(lengthOfNumList):
        minValList[num][num] = numbersList[num]
        maxValList[num][num] = numbersList[num]


    for diff in range(1, lengthOfNumList):
        for row in range(1, lengthOfNumList + 1 - diff):
            col = row + diff
            minValList[row-1][col-1], maxValList[row-1][col-1] = minMax(row-1, col-1, operatorsList, minValList, maxValList)

    return maxValList[0][lengthOfNumList-1]







if __name__ == '__main__':

    print("\nKnapsack with repetitions:", knapsackWithRepetitions(10, [6, 3, 4, 2], [30, 14, 16, 9]))
    print("Knapsack without repetitions:", knapsackWithoutRepetitions(10, [6, 3, 4, 2], [30, 14, 16, 9]))
    print("(Memoization Recursive) Knapsack without repetitions:", knapsackWithRepetitionsRecursive(10, [6, 3, 4, 2], [30, 14, 16, 9], {}))

    print("\nMaximize the value of expression 5-8+7*4-8+9 by placing parentheses anywhere:", parentheses([5, 8, 7, 4, 8, 9], ['-','+','*','-','+']))