summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/fractional_knapsack.py37
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/fractional_knapsackTest.py36
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()