Instantly share code, notes, and snippets.

@suminb /kanpsack.py
Last active Oct 27, 2016

Embed
What would you like to do?
이상한 호주 여행기 - 비용 정산 편에 소개 된 배낭 문제 코드입니다.
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]))
➜ python knapsack.py
Sum of taken values = 312967
Taken records = [9520, 58176, 74453, 7613, 18688, 19425, 21636, 21256, 71294, 10906]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment