이상한 호주 여행기 - 비용 정산 편에 소개 된 배낭 문제 코드입니다.

kanpsack.py

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]))

notes.txt

➜  python knapsack.py 
Sum of taken values = 312967
Taken records = [9520, 58176, 74453, 7613, 18688, 19425, 21636, 21256, 71294, 10906]

참고 문서

• https://en.wikipedia.org/wiki/Knapsack_problem
• http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf