Adding Two Algorithms (#102)

anubhav9199 · web-flow · commit be35813729a0 · 2020-10-06T09:03:37.000+05:30
* Fractional Knapsack Algorithm

* Longest Palindrome Substring Algorithm
diff --git a/pygorithm/dynamic_programming/fractional_knapsack.py b/pygorithm/dynamic_programming/fractional_knapsack.py
@@ -0,0 +1,67 @@
+# https://en.wikipedia.org/wiki/Continuous_knapsack_problem
+# https://www.guru99.com/fractional-knapsack-problem-greedy.html
+# https://medium.com/walkinthecode/greedy-algorithm-fractional-knapsack-problem-9aba1daecc93
+
+"""
+Author  : Anubhav Sharma
+This is a pure Python implementation of Dynamic Programming solution to the Fractional Knapsack of a given items and weights.
+The problem is  :
+Given N items and weights, to find the max weight of item to put in fractional knapsack in that given knapsack and
+return it.
+Example: Weight of knapsack to carry, Items and there weights as input will return
+         Items in fraction to put in the knapsack as per weight as output
+"""
+
+def fractional_knapsack(value: list[int], weight: list[int], capacity: int) -> tuple[int, list[int]]:
+    """
+    >>> value = [1, 3, 5, 7, 9]
+    >>> weight = [0.9, 0.7, 0.5, 0.3, 0.1]
+    >>> fractional_knapsack(value, weight, 5)
+    (25, [1, 1, 1, 1, 1])
+    >>> fractional_knapsack(value, weight, 15)
+    (25, [1, 1, 1, 1, 1])
+    >>> fractional_knapsack(value, weight, 25)
+    (25, [1, 1, 1, 1, 1])
+    >>> fractional_knapsack(value, weight, 26)
+    (25, [1, 1, 1, 1, 1])
+    >>> fractional_knapsack(value, weight, -1)
+    (-90.0, [0, 0, 0, 0, -10.0])
+    >>> fractional_knapsack([1, 3, 5, 7], weight, 30)
+    (16, [1, 1, 1, 1])
+    >>> fractional_knapsack(value, [0.9, 0.7, 0.5, 0.3, 0.1], 30)
+    (25, [1, 1, 1, 1, 1])
+    >>> fractional_knapsack([], [], 30)
+    (0, [])
+    """
+    index = list(range(len(value)))
+    ratio = [v / w for v, w in zip(value, weight)]
+    index.sort(key=lambda i: ratio[i], reverse=True)
+
+    max_value = 0
+    fractions = [0] * len(value)
+    for i in index:
+        if weight[i] <= capacity:
+            fractions[i] = 1
+            max_value += value[i]
+            capacity -= weight[i]
+        else:
+            fractions[i] = capacity / weight[i]
+            max_value += value[i] * capacity / weight[i]
+            break
+
+    return max_value, fractions
+
+
+if __name__ == "__main__":
+    n = int(input("Enter number of items: "))
+    value = input(f"Enter the values of the {n} item(s) in order: ").split()
+    value = [int(v) for v in value]
+    weight = input(f"Enter the positive weights of the {n} item(s) in order: ".split())
+    weight = [int(w) for w in weight]
+    capacity = int(input("Enter maximum weight: "))
+
+    max_value, fractions = fractional_knapsack(value, weight, capacity)
+    print("The maximum value of items that can be carried:", max_value)
+    print("The fractions in which the items should be taken:", fractions)
+
+    
diff --git a/pygorithm/dynamic_programming/longest_palindrome_substring.py b/pygorithm/dynamic_programming/longest_palindrome_substring.py
@@ -0,0 +1,75 @@
+"""
+Author  : Anubhav Sharma
+This is a pure Python implementation of Dynamic Programming solution to the longest
+palindrome substring of a given string.
+I use Manacher Algorithm which is amazing algorithm and find solution in linear time complexity.
+The problem is  :
+Given a string, to find the longest palindrome sub-string in that given string and
+return it.
+Example: aabbabbaababa as input will return
+         aabbabbaa as output
+"""
+def manacher_algo_lps(s,n):
+    """
+    PARAMETER
+    --------------
+    s = string
+    n = string_len (int)
+    manacher Algorithm is the fastest technique to find the longest palindrome substring in any given string.
+    RETURN
+    ---------------
+    Longest Palindrome String(String)
+    """
+    # variables to use
+    p = [0] * n
+    c = 0
+    r = 0
+    maxlen = 0
+
+    # Main Algorithm
+    for i in range(n):
+        mirror = 2*c-i # Finding the Mirror(i.e. Pivort to break) of the string
+        if i < r:
+            p[i] = (r - i) if (r - i) < p[mirror] else p[mirror]
+        a = i + (1 + p[i])
+        b = i - (1 + p[i])
+
+        # Attempt to expand palindrome centered at currentRightPosition i 
+        # Here for odd positions, we compare characters and 
+        # if match then increment LPS Length by ONE 
+        # If even position, we just increment LPS by ONE without 
+        # any character comparison
+        while a<n and b>=0 and s[a] == s[b]:
+            p[i] += 1
+            a += 1
+            b -= 1
+        if (i + p[i]) > r:
+            c = i
+            r = i + p[i]
+            if p[i] > maxlen:               # Track maxLPSLength
+                maxlen = p[i]
+    i = p.index(maxlen)
+    return s[i-maxlen:maxlen+i][1::2]
+
+def longest_palindrome(s: str) -> str:
+    s = '#'.join(s)
+    s = '#'+s+'#'
+
+    # Calling Manacher Algorithm
+    return manacher_algo_lps(s,len(s))
+
+def main():
+
+    # Input to enter
+    input_string = "abbbacdcaacdca"
+
+    # Calling the longest palindrome algorithm
+    s = longest_palindrome(input_string)
+    print("LPS Using Manacher Algorithm {}".format(s))
+
+# Calling Main Function
+if __name__ == "__main__":
+
+    main()
+
+    
