Fractional Knapsack done

2 files changed, 73 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
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/fractional_knapsackTest.py b/AlgoDesignAndTechniqueEdxPython/tests/fractional_knapsackTest.py
new file mode 100644
index 0000000..fda766f
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/fractional_knapsackTest.py
@@ -0,0 +1,36 @@
+'''
+Created on Sep 7, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.fractional_knapsack import getBestItem, getOptimalValue
+
+class Test(unittest.TestCase):
+
+    def testBestItem1(self):
+        values = [60, 100, 120]
+        weights = [20, 50, 30]
+        self.assertEqual(2, getBestItem(values, weights))
+
+    def testBestItem2(self):
+        values = [500]
+        weights = [30]
+        self.assertEqual(0, getBestItem(values, weights))
+    
+    def test1(self):
+        values = [44, 26,31]
+        weights = [6, 28,38]
+        capacity = 50
+        self.assertAlmostEqual(83.0526, getOptimalValue(capacity, values, weights), 4)
+        
+    def test2(self):
+        values = [60, 100, 120]
+        weights = [20,50,30]
+        capacity = 50
+        self.assertAlmostEqual(180, getOptimalValue(capacity, values, weights), 4)
+
+if __name__ == "__main__":
+    # import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()