From 7c4273cabf7202d1a7a84c675a1d5eb2d4781592 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 7 Sep 2018 14:35:48 -0500 Subject: Fractional Knapsack done --- .../sources/fractional_knapsack.py | 37 ++++++++++++++++++++++ .../tests/fractional_knapsackTest.py | 36 +++++++++++++++++++++ 2 files changed, 73 insertions(+) create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/fractional_knapsack.py create mode 100644 AlgoDesignAndTechniqueEdxPython/tests/fractional_knapsackTest.py 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() -- cgit v1.2.3