Skip to content

Instantly share code, notes, and snippets.

@suminb 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]
@suminb

This comment has been minimized.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.