1 files changed, 37 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/fractional_knapsack.py b/AlgoDesignAndTechniqueEdxPython/sources/fractional_knapsack.py
new file mode 100644
index 0000000..898d8da
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/fractional_knapsack.py
@@ -0,0 +1,37 @@
+# Uses python3
+import sys
+def getBestItem(values, weights):
+    maxValueWeight = 0
+    bestItem = 0
+    for i in range(len(values)):
+        if weights[i] >0:
+            if values[i]/weights[i] > maxValueWeight:
+                maxValueWeight = values[i]/weights[i]
+                bestItem = i
+    return bestItem
+
+
+def getOptimalValue(capacity, values, weights):
+    totalValue = 0
+    tempWeight = 0
+    
+    for _ in range(len(values)):
+        if capacity==0:
+            return totalValue
+        i = getBestItem(values, weights)
+        if weights[i] < capacity:
+            tempWeight = weights[i]
+        else:
+            tempWeight = capacity
+        totalValue = totalValue + tempWeight*values[i]/weights[i]
+        weights[i] = weights[i]-tempWeight
+        capacity = capacity-tempWeight
+    return totalValue
+
+if __name__ == "__main__":
+    data = list(map(int, sys.stdin.read().split()))
+    n, capacity = data[0:2]
+    values = data[2:(2 * n + 2):2]
+    weights = data[3:(2 * n + 2):2]
+    opt_value = getOptimalValue(capacity, values, weights)
+    print("{:.10f}".format(opt_value))
+\ No newline at end of file