Skip to content

Instantly share code, notes, and snippets.

@haje01
Created Mar 2, 2015
Embed
What would you like to do?
cache = None
def memoize(fn):
global cache
def helper(w, ts, i):
if cache[w][i] == -1:
cache[w][i] = fn(w, ts, i)
return cache[w][i]
return helper
@memoize
def eager(w, ts, i):
if len(ts) < i + 1:
return 0
n, s, e = ts[i]
ne = eager(w, ts, i + 1)
if w < s:
return ne
te = eager(w - s, ts, i + 1) + e
return max(te, ne)
def collect(rv, me, w, ts, i):
if len(ts) < i + 1:
return
n, s, e = ts[i]
te = eager(w - s, ts, i + 1) + e
if te == me and w >= s:
rv.append(i)
collect(rv, me - e, w - s, ts, i + 1)
else:
collect(rv, me, w, ts, i + 1)
def solv(w, ts):
global cache
cache = [[-1] * 101 for i in range(1001)]
me = eager(w, ts, 0)
rv = []
collect(rv, me, w, ts, 0)
return [me, len(rv), [ts[i][0] for i, t in enumerate(ts) if i in rv]]
if __name__ == "__main__":
c = int(raw_input())
for i in xrange(c):
ts = []
n, w = [int(i) for i in raw_input().split()]
for p in xrange(n):
t = raw_input().split()
ts.append([t[0], int(t[1]), int(t[2])])
rv = solv(w, ts)
print rv[0], rv[1]
for t in rv[2]:
print t
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment