Instantly share code, notes, and snippets.

# suminb/kanpsack.py

Last active October 27, 2016 15:41
Show Gist options
• Save suminb/e9b255dc1afdf3b586a43ce2a28e960a to your computer and use it in GitHub Desktop.
이상한 호주 여행기 - 비용 정산 편에 소개 된 배낭 문제 코드입니다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 values = [ 16199, 10906, 3382, 84725, 71294, 36372, 21256, 18555, 21636, 19425, 18688, 10482, 7613, 74453, 58176, 50942, 26950, 26582, 9589, 9520, 210198, 50818, 36992, 17732, 16953, 9971, 8031, 5247, 372309] limit = 312967 def m(i, limit, values, taken, cache): """Calculates the maximum value that can be attained with total value less than or equal to `limit`. :param i: The current index :param limit: The maximum total value :param values: A list if values :param taken: Keeps track of which (i, limit) pairs have taken """ if i < 0: return 0 else: curr = values[i] key = (i, limit) try: return cache[key] except KeyError: pass if curr > limit: value = m(i - 1, limit, values, taken, cache) else: left = m(i - 1, limit, values, taken, cache) right = m(i - 1, limit - curr, values, taken, cache) + curr if right > left: taken[key] = 1 value = right else: value = left cache[key] = value return value def track_solutions(n, limit, values, taken): k = limit for i in range(n, -1, -1): if (i, k) in taken: yield i k -= values[i] if __name__ == '__main__': taken, cache = {}, {} n = len(values) - 1 v = m(n, limit, values, taken, cache) s = track_solutions(n, limit, values, taken) print('Sum of taken values = {}'.format(v)) print('Taken records = {}'.format([values[i] for i in s]))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ➜ python knapsack.py Sum of taken values = 312967 Taken records = [9520, 58176, 74453, 7613, 18688, 19425, 21636, 21256, 71294, 10906]