이상한 호주 여행기 - 비용 정산 편에 소개 된 배낭 문제 코드입니다.
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])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
suminb commentedOct 24, 2016
참고 문서