knapsack.py

from collections import defaultdict as dd
from itertools import product


def solve(limit, values, weights):
    """ Solution for the unbounded knapsack problem. """
    weights, values = zip(*sorted([(w, v) for w, v in zip(weights, values)]))
    inf = limit + 1
    maxv = [0 for _ in xrange(limit + 1)]
    for value, weight in zip(values, weights):
        if weight <= limit:
            maxv[weight] = max(maxv[weight], value)

    for c in xrange(limit + 1):
        for i, w in enumerate(weights):
            if c - w < 0:
                break
            maxv[c] = max(maxv[c], maxv[c - w] + values[i])
    
    return maxv[limit]


def brute_solve_01(limit, values, weights):
    """ Bruteforce solution for the 0-1 knapsack problem. """
    n = len(values)
    ret = 0
    for indexes in product(*[[0, 1] for _ in xrange(n)]):
        cw, cv = 0, 0
        for i in indexes:
            cw += weights[i]
            cv += values[i]
        if cw <= limit:
            ret = max(cv, ret)
    return ret


if __name__ == "__main__":
    limit = int(raw_input().strip())
    values = map(int, raw_input().strip().split())
    weights = map(int, raw_input().strip().split())
    print solve(limit, values, weights)