Problem:


泥棒

宝物がたくさん収蔵されている博物館に、泥棒が大きな風呂敷を一つだけ持って忍び込みました。盗み出したいものはたくさんありますが、風呂敷が耐えられる重さが限られており、これを超えると風呂敷が破れてしまいます。そこで泥棒は、用意した風呂敷を破らず且つ最も価値が高くなるようなお宝の組み合わせを考えなくてはなりません。

風呂敷が耐えられる重さ W、および博物館にある個々のお宝の価値と重さを読み込んで、重さの総和が W を超えない範囲で価値の総和が最大になるときの、お宝の価値総和と重さの総和を出力するプログラムを作成してください。ただし、価値の総和が最大になる組み合わせが複数あるときは、重さの総和が小さいものを出力することとします。

Input

複数のデータセットが与えられます。各データセットは以下のような形式で与えられます。

W
N
v1,w1
v2,w2
:
vN,wN

１行目に風呂敷の耐えられる重さを表す整数 W (W ≤ 1,000)、２行目にお宝の数 N (1 ≤ N ≤ 1,000) が与えられます。続く N 行に i 番目のお宝の価値を表す整数 vi (0 ≤ vi ≤ 10,000) とその重さを表す整数 wi (0 ≤ wi ≤ W) の組がそれぞれ１行に与えられます。

W が 0 のとき入力の最後とします。データセットの数は 50 を超えません。

Output

各データセットに対して以下のように出力して下さい。

Case データセットの番号:
風呂敷に入れたお宝の価値総和
そのときのお宝の重さの総和

Sample Input

50
5
60,10
100,20
120,30
210,45
10,4
50
5
60,10
100,20
120,30
210,45
10,4
0

Output for the Sample Input

Case 1:
220
49
Case 2:
220
49



Sample input:
50
5
60,10
100,20
120,30
210,45
10,4
50
5
60,10
100,20
120,30
210,45
10,4
0


Sample output:
Case 1:
220
49
Case 2:
220
49

Submission status: Runtime Error

Solution code:
import itertools

count = 0
while True:
	w = int(raw_input())
	if w == 0:
		break
	m = int(raw_input())
	n = [0 for _ in xrange(m)]
	h = [0 for _ in xrange(m)]
	count += 1
	
	for i in xrange(m):
		n[i],h[i] = map(int,raw_input().split(","))
	
	js= []
	jk = []
	for i in xrange(m):
		lis = list(itertools.combinations(h,  m - i))
		for j in lis:
			jk.append(sum(j))
		las = list(itertools.combinations(n,  m - i))
		for j in las:
			js.append(sum(j))
	
	jc = list(filter(lambda x: x < w, jk))
	jc.sort()
	js.sort()
	print "Case " + str(count) + ":"
	print js[len(jc) - 1]
	print jc[len(jc) - 1]

Submission status: Runtime Error

Solution code:
import itertools

count = 0
while True:
	w = int(raw_input())
	if w == 0:
		break
	m = int(raw_input())
	n = [0 for _ in xrange(m)]
	h = [0 for _ in xrange(m)]
	count += 1
	
	for i in xrange(m):
		n[i],h[i] = map(int,raw_input().split(","))
	
	tr = []
	ty = []
	for i in xrange(m):
		lis = list(itertools.combinations(h,  m - i))
		for j in lis:
			tr.append(sum(j))
		las = list(itertools.combinations(n,  m - i))
		for j in las:
			ty.append(sum(j))
	
	te = list(filter(lambda x: x < w, tr))
	te.sort()
	ty.sort()
	print "Case " + str(count) + ":"
	print ty[len(te) - 1]
	print te[len(te) - 1]

Submission status: Runtime Error

Solution code:
import itertools

count = 0
if __name__ == "__main__":
	while True:
		w = int(raw_input())
		if w == 0:
			break
		m = int(raw_input())
		n = [0 for _ in xrange(m)]
		h = [0 for _ in xrange(m)]
		count += 1
	
		for i in xrange(m):
			n[i],h[i] = map(int,raw_input().split(","))
	
		tr = []
		ty = []
		for i in xrange(m):
			lis = list(itertools.combinations(h,  m - i))
			for j in lis:
				tr.append(sum(j))
			las = list(itertools.combinations(n,  m - i))
			for j in las:
				ty.append(sum(j))
	
		te = list(filter(lambda x: x < w, tr))
		te.sort()
		ty.sort()
		print "Case " + str(count) + ":"
		print ty[len(te) - 1]
		print te[len(te) - 1]

Submission status: Runtime Error

Solution code:


def rec(i, j):
	if dp[i][j] != -1:
		return dp[i][j]
	if i == N:
		ans = 0, W - j
	elif j < wl[i]:
		ans = rec(i + 1, j)
	else:
		v1, w1 = rec(i + 1, j)
		v2, w2 = rec(i + 1, j - wl[i])
		v2 += vl[i]
		if v1 > v2:
			ans = v1, w1
		elif v1 < v2:
			ans = v2, w2
		elif v1 == v2:
			if w1 < w2:
				ans = v1, w1
			else:
				ans = v2, w2
	dp[i][j] = ans
	return ans

case = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	dp = [[-1 for j in range(2000)] for i in range(2000)]
	v, w = rec(0, W)
	
	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

Submission status: Runtime Error

Solution code:


def rec(i, j):
	if dp[i][j] != -1:
		return dp[i][j]
	if i == N:
		ans = 0, W - j
	elif j < wl[i]:
		ans = rec(i + 1, j)
	else:
		v1, w1 = rec(i + 1, j)
		v2, w2 = rec(i + 1, j - wl[i])
		v2 += vl[i]
		if v1 > v2:
			ans = v1, w1
		elif v1 < v2:
			ans = v2, w2
		elif v1 == v2:
			if w1 < w2:
				ans = v1, w1
			else:
				ans = v2, w2
	dp[i][j] = ans
	return ans

case = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	dp = [[-1 for j in range(1100)] for i in range(1100)]
	v, w = rec(0, W)
	
	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

Submission status: Runtime Error

Solution code:


def rec(i, j):
	if dp[i][j] != -1:
		return dp[i][j]
	if i == N:
		ans = 0, W - j
	elif j < wl[i]:
		ans = rec(i + 1, j)
	else:
		v1, w1 = rec(i + 1, j)
		v2, w2 = rec(i + 1, j - wl[i])
		v2 += vl[i]
		if v1 > v2:
			ans = v1, w1
		elif v1 < v2:
			ans = v2, w2
		elif v1 == v2:
			if w1 < w2:
				ans = v1, w1
			else:
				ans = v2, w2
	dp[i][j] = ans
	return ans

case = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	dp = [[-1 for j in range(2500)] for i in range(2500)]
	v, w = rec(0, W)

	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

Submission status: Runtime Error

Solution code:


def rec(i, j):
	if dp[i][j] != -1:
		return dp[i][j]
	if i == N:
		ans = (0, W - j)
	elif j < wl[i]:
		ans = rec(i + 1, j)
	else:
		(v1, w1) = rec(i + 1, j)
		(v2, w2) = rec(i + 1, j - wl[i])
		v2 += vl[i]
		if v1 > v2:
			ans = (v1, w1)
		elif v1 < v2:
			ans = (v2, w2)
		elif v1 == v2:
			if w1 < w2:
				ans = (v1, w1)
			else:
				ans = (v2, w2)
	dp[i][j] = ans
	return ans

case = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	dp = [[-1 for j in range(2500)] for i in range(2500)]
	(v, w) = rec(0, W)

	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

Submission status: Runtime Error

Solution code:


def rec(i, j):
	if 3000 < i or 3000 < j:
		while True:
			print("aaa")

	if dp[i][j] != -1:
		return dp[i][j]
	if i == N:
		ans = (0, W - j)
	elif j < wl[i]:
		ans = rec(i + 1, j)
	else:
		(v1, w1) = rec(i + 1, j)
		(v2, w2) = rec(i + 1, j - wl[i])
		v2 += vl[i]
		if v1 > v2:
			ans = (v1, w1)
		elif v1 < v2:
			ans = (v2, w2)
		elif v1 == v2:
			if w1 < w2:
				ans = (v1, w1)
			else:
				ans = (v2, w2)
	dp[i][j] = ans
	return ans

case = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	dp = [[-1 for j in range(2500)] for i in range(2500)]
	(v, w) = rec(0, W)

	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

Submission status: Runtime Error

Solution code:


def rec(i, j):
	#print("rec({}, {}) called".format(i, j))
	"""
	if dp[i][j] != -1:
		return dp[i][j]
	"""
	if i in dphash and j in dphash[i]:
		return dphash[i][j]
	if i == N:
		ans = (0, W - j)
	elif j < wl[i]:
		ans = rec(i + 1, j)
	else:
		(v1, w1) = rec(i + 1, j)
		(v2, w2) = rec(i + 1, j - wl[i])
		v2 += vl[i]
		if v1 > v2:
			ans = (v1, w1)
		elif v1 < v2:
			ans = (v2, w2)
		elif v1 == v2:
			if w1 < w2:
				ans = (v1, w1)
			else:
				ans = (v2, w2)
	#dp[i][j] = ans
	if i in dphash:
		dphash[i][j] = ans
	else:
		dphash[i] = {}
		dphash[i][j] = ans

	return ans

case = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	#dp = [[-1 for j in range(2500)] for i in range(2500)]
	dphash = {}
	(v, w) = rec(0, W)

	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

Submission status: Runtime Error

Solution code:


def rec(i, j):
	#print("rec({}, {}) called".format(i, j))
	if i in dphash and j in dphash[i]:
		return dphash[i][j]
	if i == N:
		ans = (0, W - j)
	elif j < wl[i]:
		ans = rec(i + 1, j)
	else:
		(v1, w1) = rec(i + 1, j)
		(v2, w2) = rec(i + 1, j - wl[i])
		v2 += vl[i]
		if v1 > v2:
			ans = (v1, w1)
		elif v1 < v2:
			ans = (v2, w2)
		elif v1 == v2:
			if w1 < w2:
				ans = (v1, w1)
			else:
				ans = (v2, w2)
	#dp[i][j] = ans
	if i in dphash:
		dphash[i][j] = ans
	else:
		dphash[i] = {}
		dphash[i][j] = ans

	return ans

case = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	#dp = [[-1 for j in range(2500)] for i in range(2500)]
	dphash = {}
	(v, w) = rec(0, W)

	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

Submission status: Runtime Error

Solution code:


def rec(i, j):
	#print("rec({}, {}) called".format(i, j))
	if i in dphash and j in dphash[i]:
		return dphash[i][j]
	if i == N:
		ans = (0, W - j)
	elif j < wl[i]:
		ans = rec(i + 1, j)
	else:
		(v1, w1) = rec(i + 1, j)
		(v2, w2) = rec(i + 1, j - wl[i])
		v2 += vl[i]
		if v1 > v2:
			ans = (v1, w1)
		elif v1 < v2:
			ans = (v2, w2)
		elif v1 == v2:
			if w1 < w2:
				ans = (v1, w1)
			else:
				ans = (v2, w2)
	#dp[i][j] = ans
	if i in dphash:
		dphash[i][j] = ans
	else:
		dphash[i] = {}
		dphash[i][j] = ans

	return ans

casea = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	#dp = [[-1 for j in range(2500)] for i in range(2500)]
	dphash = {}
	(v, w) = rec(0, W)

	print("Case {}:".format(casea))
	print(v)
	print(w)
	casea += 1

Submission status: Runtime Error

Solution code:
case = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	dp = [[[0, 0] for j in range(W + 1)] for i in range(N + 1)]
	for i in range(N - 1, -1, -1):
		for j in range(0, W + 1):
			if j < wl[i]:
				dp[i][j] = dp[i + 1][j]
			else:
				if dp[i + 1][j][0] > dp[i+1][j - wl[i]][0] + vl[i]:
					dp[i][j] = dp[i + 1][j]
				elif dp[i + 1][j][0] < dp[i+1][j - wl[i]][0] + vl[i]:
					dp[i][j] = dp[i+1][j - wl[i]]
					dp[i][j][0] += vl[i]
				elif dp[i + 1][j][0] = dp[i+1][j - wl[i]][0] + vl[i]:
					
	v, w = dp[0][W]

	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

Submission status: Runtime Error

Solution code:
times=0
while True:
    times+=1
    W=int(input())
    n=int(input())
    if W==0:
        break
    w=[0]*n
    v=[0]*n
    for i in range(n):
        v[i],w[i]=map(int,input().split(","))
    dp=[[0]*(W+1) for i in range(n+1)]
    for i in range(n):
        for j in range(W+1):
            if j<w[i]:
                dp[i+1][j]=dp[i][j]
            else:
                dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
    MIN=0
    for i in range(W+1):
        if dp[n][i]==dp[n][W]:
            MIN=i
            break
    print("Case %d:"%times)
    print(dp[n][W])
    print(MIN)

Submission status: Runtime Error

Solution code:
def dfs_dp(w, v, N, W, index, dp):
    if (dp[index][W][0] != -1):
        return dp[index][W]
    if index==N: return [0,0]
    if W<w[index]: return dfs_dp(w, v, N, W, index + 1, dp)

    temp1=dfs_dp(w, v, N, W, index + 1, dp)
    temp=dfs_dp(w, v, N, W - w[index], index + 1, dp)
    temp2=[v[index] + temp[0],w[index]+temp[1]]
    if temp1[0]==temp2[0]:
        if temp1[1]<temp2[1]:
            ret=temp1
        else: ret=temp2
    elif temp1[0]>temp2[0]:
        ret=temp1
    else: ret=temp2

    dp[index][W]=ret
    return ret


count=1
W=int(input())
while(W!=0):
    N=int(input())
    w=[]
    v=[]
    dp=[[[-1,-1] for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        a,b=input().split(',')
        v.append(int(a))
        w.append(int(b))

    sum=dfs_dp(w,v,N,W,0,dp)

    print("Case "+str(count)+":")
    print(sum[0])
    print(sum[1])
    W=int(input())
    count+=1

Submission status: Runtime Error

Solution code:
# i????????\??????????????§??????j??§??????(?????§??????, ??????????????????)
def ns(vs, ws, i, j, dp):
    if dp[i][j][0] != -1:
        return dp[i][j]
    if i == len(vs):
        return [0, 0]
    else:
        if ws[i] > j:
            dp[i][j] = ns(vs, ws, i+1, j, dp)
            return dp[i][j] 
        else:
            tmp = ns(vs, ws, i+1, j-ws[i], dp)
            dp[i][j] = max(ns(vs, ws, i+1, j, dp), [vs[i]+tmp[0], ws[i]+tmp[1]], key = lambda x: x[0])
            return dp[i][j]

casenum = 1
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    vs, ws = [], []
    for _ in range(N):
        v, w = map(int, input().split(','))
        vs.append(v)
        ws.append(w)

    dp = [[[-1, -1] for _ in range(W+1)] for __ in range(N+1)]
    v, w = ns(vs, ws, 0, W, dp)
    print('Case ' + str(casenum) + ':')
    print(v)
    print(w)
    casenum += 1

Submission status: Runtime Error

Solution code:
# i????????\??????????????§??????j??§??????(?????§??????, -??????????????????)
def ns(vs, ws, i, j, dp):
    if dp[i][j][0] != -1:
        return dp[i][j]
    if i == len(vs):
        return [0, 0]
    else:
        if ws[i] > j:
            dp[i][j] = ns(vs, ws, i+1, j, dp)
            return dp[i][j] 
        else:
            tmp = ns(vs, ws, i+1, j-ws[i], dp)
            dp[i][j] = max(ns(vs, ws, i+1, j, dp), [vs[i]+tmp[0], -ws[i]+tmp[1]], key = lambda x: (x[0], x[1]))
            return dp[i][j]

casenum = 1
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    vs, ws = [], []
    for _ in range(N):
        v, w = map(int, input().split(','))
        vs.append(v)
        ws.append(w)

    dp = [[[-1, -1] for _ in range(W+1)] for __ in range(N+1)]
    v, w = ns(vs, ws, 0, W, dp)
    print('Case ' + str(casenum) + ':')
    print(v)
    print(-w)
    casenum += 1

Submission status: Runtime Error

Solution code:
def ns(vs, ws, i, j, dp):
    if dp[i][j][0] != -1:
        return dp[i][j]
    if i == len(vs):
        return [0, 0]
    else:
        if ws[i] > j:
            dp[i][j] = ns(vs, ws, i+1, j, dp)
            return dp[i][j] 
        else:
            tmp = ns(vs, ws, i+1, j-ws[i], dp)
            dp[i][j] = max(ns(vs, ws, i+1, j, dp), [vs[i]+tmp[0], -ws[i]+tmp[1]], key = lambda x: (x[0], x[1]))
            return dp[i][j]

casenum = 1
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    vs, ws = [], []
    for _ in range(N):
        v, w = map(int, input().split(','))
        vs.append(v)
        ws.append(w)

    dp = [[[-1, -1] for _ in range(W+1)] for __ in range(N+1)]
    v, w = ns(vs, ws, 0, W, dp)
    print('Case ' + str(casenum) + ':')
    print(v)
    print(-w)
    casenum += 1

Submission status: Runtime Error

Solution code:
# coding: utf-8

    count += 1

Submission status: Runtime Error

Solution code:
# coding: utf-8

    count = 1

Submission status: Runtime Error

Solution code:
def get():
    p,w = map(int, raw_input().split(","))
    for i in range(W-w,-1,-1):
        if bag[i] > 0 and bag[i]+p > bag[i+w]:
            bag[i+w] = bag[i]+p
    else:
        if p > bag[w]: bag[w] = p
    return
 
c = 1
while True:
    W = int(raw_input())
    if W == 0: break
    bag = [0]*(W+1)
    N = int(raw_input())
    for i in range(N): get()
    w_all = max(bag)
    money = bag.index(w_all)
    print "Case {}:\n{}\n{}".format(c,w_all,money)
    c += 1

Submission status: Runtime Error

Solution code:
from itertools import combinations
case = 0
while True :
    limit = int(input())
    if limit == 0 : break
    case += 1
    number = int(input())
    
    value, weight = [], []
    for _ in range(number) :
        a, b = input().split(',')
        value.append(int(a))
        weight.append(int(b))
    
    temp1, temp2 = [], []
    for _ in range(1, number+1) : 
        temp1.append(list(combinations(value, _)))
        temp2.append(list(combinations(weight, _)))
    temp1, temp2 = sum(temp1, []), sum(temp2, [])
    value, weight = [], []
    for _ in temp1 : value.append(sum(_))
    for _ in temp2 : weight.append(sum(_))
    
    result = [0, 0]
    for _ in range(len(temp1)) :
        if result[0] < value[_] and weight[_] =< limit :
            result = value[_], weight[_]
        elif result[0] == value and weight[_] < result[1] :
            result = value[_], weight[_]
    print('Case {}:'.format(case))
    print(result[0])
    print(result[1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools

def solve():
    cache = dict()
    def loop(i, w):
        if (i, w) in cache:
            return cache[i, w]
        if i == N:
            return (0, 0)
        cache[i, w] = loop(i + 1, w)
        if v[i][1] <= w:
            t = loop(i + 1, w - v[i][1])
            cache[i, w] = max(cache[i, w], (t[0] + v[i][0], t[1] + v[i][1]), key=lambda u: u[0])
        return cache[i, w]
    return loop(0, W)

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    v = [tuple(map(int, input().split(','))) for _ in range(N)]
    optim = solve()
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))

Submission status: Runtime Error

Solution code:
import itertools

def solve():
    cache = {}
    def loop(i, w):
        if (i, w) in cache:
            return cache[i, w]
        if i == N:
            return (0, 0)
        cache[i, w] = loop(i + 1, w)
        if v[i][1] <= w:
            t = loop(i + 1, w - v[i][1])
            cache[i, w] = max(cache[i, w], (t[0] + v[i][0], t[1] + v[i][1]), key=lambda u: u[0])
        return cache[i, w]
    return loop(0, W)

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    v = [tuple(map(int, input().split(','))) for _ in range(N)]
    optim = solve()
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))

Submission status: Runtime Error

Solution code:
import itertools

def solve(W, N, v):
    cache = {}
    def loop(i, w):
        if (i, w) in cache:
            return cache[i, w]
        if i == N:
            return (0, 0)
        cache[i, w] = loop(i + 1, w)
        if v[i][1] <= w:
            t = loop(i + 1, w - v[i][1])
            cache[i, w] = max(cache[i, w], (t[0] + v[i][0], t[1] + v[i][1]), key=lambda u: u[0])
        return cache[i, w]
    return loop(0, W)

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    v = [tuple(map(int, input().split(','))) for _ in range(N)]
    optim = solve(W, N, v)
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools

def solve(W, N, v):
    cache = [[None for _ in range(W + 1)] for _ in range(N)]
    def loop(i, w):
        if i == N:
            return (0, 0)
        if cache[i][w] is not None:
            return cache[i][w]
        cache[i][w] = loop(i + 1, w)
        if v[i][1] <= w:
            t = loop(i + 1, w - v[i][1])
            cache[i][w] = max(cache[i][w], (t[0] + v[i][0], t[1] + v[i][1]), key=lambda u: u[0])
        return cache[i][w]
    return loop(0, W)

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    v = [tuple(map(int, input().split(','))) for _ in range(N)]
    optim = solve(W, N, v)
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools

def solve(W, N, v):
    cache = {}
    def loop(i, w):
        if i == N:
            return (0, 0)
        if (i, w) in cache:
            return cache[i, w]
        cache[i, w] = loop(i + 1, w)
        if v[i][1] <= w:
            t = loop(i + 1, w - v[i][1])
            t = (t[0] + v[i][0], t[1] + v[i][1])
            if cache[i, w][0] < t[0] or cache[i, w][0] == t[0] and t[1] < cache[i, w][1]:
                cache[i, w] = t
        return cache[i, w]
    return loop(0, W)

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    v = [tuple(map(int, input().split(','))) for _ in range(N)]
    optim = solve(W, N, v)
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))

Submission status: Runtime Error

Solution code:
c=0
for W in iter(input,'0\n'):
 c+=1
 W=int(W)
 dp=[0]*-~W
 for _ in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):
   if dp[i]<dp[i-w]+v:dp[i]=dp[i-w]+v
 for i in range(W+1):
  if dp[W]==dp[i]:print(f'Case {c}:\n{dp[W]}\n{i}');break

Submission status: Runtime Error

Solution code:
case = 0
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    case += 1
    # a list of [itemValue, itemWeight]
    items = [list(map(int,input().split(','))) for i in range(N)]
    dp = {}
    def bestVW(item, capa):
        if (item,capa) in dp:
            return dp[(item,capa)]
        elif item == 0:
            bestVWForCapa = items[item] if items[item][1] <= capa else [0,0]
            dp[(item,capa)] = bestVWForCapa
            return bestVWForCapa
        else:
            if items[item][1] > capa:
                bestVWForCapa = bestVW(item-1, capa)
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
            else:
                pickedVW = bestVW(item-1,capa)
                notPickedVW = list(map(sum, zip(items[item], bestVW(item-1, capa-items[item][1]))))
                bestVWForCapa = pickedVW if pickedVW[0] > notPickedVW[0] else notPickedVW 
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
    print('Case ',case, ':', sep='')
    print('\n'.join(map(str,bestVW(N-1,W))))

Submission status: Runtime Error

Solution code:
case = 0
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    case += 1
    # a list of [itemValue, itemWeight]
    items = [list(map(int,input().split(','))) for i in range(N)]
    dp = {}
    def bestVW(item, capa):
        if (item,capa) in dp:
            return dp[(item,capa)]
        elif item == 0:
            bestVWForCapa = items[item] if items[item][1] <= capa else [0,0]
            dp[(item,capa)] = bestVWForCapa
            return bestVWForCapa
        else:
            if items[item][1] > capa:
                bestVWForCapa = bestVW(item-1, capa)
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
            else:
                pickedVW = bestVW(item-1,capa)
                notPickedVW = list(map(sum, zip(items[item], bestVW(item-1, capa-items[item][1]))))
                bestVWForCapa = pickedVW if pickedVW[0] > notPickedVW[0] else notPickedVW 
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
    msg = 'Case '+case+':\n'
    print(msg)
    print('\n'.join(map(str,bestVW(N-1,W))))

Submission status: Runtime Error

Solution code:
case = 0
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    case += 1
    # a list of [itemValue, itemWeight]
    items = [list(map(int,input().split(','))) for i in range(N)]
    dp = {}
    def bestVW(item, capa):
        if (item,capa) in dp:
            return dp[(item,capa)]
        elif item == 0:
            bestVWForCapa = items[item] if items[item][1] <= capa else [0,0]
            dp[(item,capa)] = bestVWForCapa
            return bestVWForCapa
        else:
            if items[item][1] > capa:
                bestVWForCapa = bestVW(item-1, capa)
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
            else:
                pickedVW = bestVW(item-1,capa)
                notPickedVW = list(map(sum, zip(items[item], bestVW(item-1, capa-items[item][1]))))
                bestVWForCapa = pickedVW if pickedVW[0] > notPickedVW[0] else notPickedVW 
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
    msg = "Case "+str(case)+":"
    print(msg)
    print('\n'.join(map(str,bestVW(N-1,W))))

Submission status: Runtime Error

Solution code:
case=0
while True:
    case+=1
    W=input()
    if W==0:break
    print "Case {}:".format(case)
    dp=[0]*1000
    w=[0]*1000
    v=[0]*1000
    n=input()
    for i in xrange(n):
        v[i],w[i]=map(int,raw_input().strip().split(","))
    for i in xrange(n):
        for j in xrange(W,-1,-1):
            if j+w[i]<=W:
                dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i])
    print max(dp)
    print dp.index(max(dp))

Submission status: Runtime Error

Solution code:
num=1
maxw=input()
while maxw<>0:
    N=input()
    ws,ps=[],[]
    for i in range(N):
        tmp=input()
        ws.append(tmp[1])
        ps.append(tmp[0])
    dp=[[0]*(maxw+1) for i in range(len(ws)+1)]
    ret=0
    for i in range(len(ws)):
        for j in range(maxw+1):
            if (j+ws[i])<=maxw:
                dp[i+1][j+ws[i]]=max(dp[i+1][j+ws[i]],dp[i][j]+ps[i])
                ret=max(dp[i+1][j+ws[i]],ret)
    print "Case %d:"%num
    print ret
    print dp[len(ws)].index(ret)
    num+=1
    maxw=input()

Submission status: Runtime Error

Solution code:
num=1
while True:
    maxw=input()
    if maxw==0:break
    N=input()
    ws,ps=[0]*N,[0]*N
    for i in xrange(N):
        ps[i],ws[i]=map(int,raw_input().strip().split(","))
    dp=[[0]*(maxw+1) for i in range(len(ws)+1)]
    ret=0
    for i in range(len(ws)):
        for j in range(maxw+1):
            if (j+ws[i])<=maxw:
                dp[i+1][j+ws[i]]=max(dp[i+1][j+ws[i]],dp[i][j]+ps[i])
                ret=max(dp[i+1][j+ws[i]],ret)
    print "Case %d:"%num
    print ret
    print dp[len(ws)].index(ret)
    num+=1

Submission status: Runtime Error

Solution code:
num=1
while True:
    maxw=input()
    if maxw==0:break
    N=input()
    ws,ps=[0]*N,[0]*N
    for i in xrange(N):
        ps[i],ws[i]=map(int,raw_input().strip().split(","))
    dp=[[0]*(maxw+1) for i in range(len(ws)+1)]
    ret=0
    for i in range(len(ws)):
        for j in range(maxw+1):
            if (j+ws[i])<=maxw:
                dp[i+1][j+ws[i]]=max(dp[i+1][j+ws[i]],dp[i][j]+ps[i])
                ret=max(dp[i+1][j+ws[i]],ret)
    print "Case {}:".format(num)
    print ret
    print dp[len(ws)].index(ret)
    num+=1

Submission status: Runtime Error

Solution code:
num=1
while True:
    maxw=input()
    if maxw==0:break
    N=input()
    ws,ps=[0]*N,[0]*N
    for i in range(N):
        ps[i],ws[i]=map(int,raw_input().strip().split(","))
    #dp=[[0]*(maxw+1) for i in range(N+1)]
    ret=0
    for i in range(N):
        for j in range(maxw+1):
            if (j+ws[i])<=maxw:
                dp[i+1][j+ws[i]]=max(dp[i+1][j+ws[i]],dp[i][j]+ps[i])
                ret=max(dp[i+1][j+ws[i]],ret)
    print "Case %d:"%num
    print ret
    print dp[len(ws)].index(ret)
    num+=1

Submission status: Runtime Error

Solution code:

import sys
import itertools

class Treasure:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight


def solv(treasures, w_limit):
    comb = t_combinations(treasures)
    ts = filter(lambda x: t_sum_weight(x) <= w_limit, comb)
    max_value = max(map(lambda x: t_sum_value(x), ts))
    ts2 = filter(lambda x: t_sum_value(x) == max_value, ts)
    if len(ts2) == 1:
        return (ts2[0].value, ts2[0].weight)
    else:
        rt = rightest(ts2)
        return (t_sum_value(rt), t_sum_weight(rt))


def t_combinations(t):
    l = len(t)
    r = []
    for x in range(1, l+1):
        for y in itertools.combinations(t, x):
            r.append(y)
    return r


def t_sum_weight(t):
    return sum(map(lambda x: x.weight, t))


def t_sum_value(t):
    return sum(map(lambda x: x.value, t))


def rightest(ts):
    return reduce(lambda a, b: take_right(a, b), ts)


def take_right(a, b):
    if t_sum_weight(a) <= t_sum_weight(b):
        return a
    else:
        return b


case = 0

while True:
    weight_limit = int(sys.stdin.readline())
    case += 1
    if weight_limit == 0:
        exit()
    n = int(sys.stdin.readline())
    treasures = []
    for i in range(n):
        v, w = map(int, sys.stdin.readline().split(','))
        treasures.append(Treasure(v, w))
    value, weight = solv(treasures, weight_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight

Submission status: Runtime Error

Solution code:

import sys
import itertools


class Treasure:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight



def solv(treasures, w_limit):
    comb = t_combinations(treasures)
    ts = filter(lambda x: t_sum_weight(x) <= w_limit, comb)
    max_value = max(map(lambda x: t_sum_value(x), ts))
    ts2 = filter(lambda x: t_sum_value(x) == max_value, ts)
    if len(ts2) == 1:
        return (ts2[0].value, ts2[0].weight)
    else:
        rt = rightest(ts2)
        return (t_sum_value(rt), t_sum_weight(rt))


def t_combinations(t):
    l = len(t)
    r = []
    for x in range(1, l+1):
        for y in itertools.combinations(t, x):
            r.append(y)
    return r


def t_sum_weight(ts):
    return sum(map(lambda x: x.weight, ts))


def t_sum_value(ts):
    return sum(map(lambda x: x.value, ts))


def rightest(tss):
    return reduce(lambda a, b: take_right(a, b), tss)


def take_right(a, b):
    if t_sum_weight(a) <= t_sum_weight(b):
        return a
    else:
        return b


case = 0

while True:
    weight_limit = int(sys.stdin.readline())
    case += 1
    if weight_limit == 0:
        exit()
    n = int(sys.stdin.readline())
    treasures = []
    for i in range(n):
        v, w = map(int, sys.stdin.readline().split(','))
        treasures.append(Treasure(v, w))
    value, weight = solv(treasures, weight_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import count, combinations

for case in count(1):
    W = int(stdin.readline())
    if not W:
        break

    N = int(stdin.readline())
    data = []
    for _ in range(N):
        data.append([int(s) for s in stdin.readline().split(',')])

    total = []
    for i in range(1, N+1):
        for cmb in combinations(data, i):
            tv, tw = 0, 0
            for value, weight in cmb:
                tv += value
                tw += weight
            if tw < W:
                total.append((tv, tw))

    tv, tw = max(total, key=lambda(tv, tw): (tv, -tw))
    print('Case {}:\n{}\n{}'.format(case, tv, tw))

Submission status: Runtime Error

Solution code:
r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

while True:
    n = int(raw_input())
    if n == 0:
        break
    count = 0
    for i in range(n/2):
        if p[i] == 1:
            m = n - (i+1)
            if p[m-1] == 1:
                count += 1
    print count

Submission status: Runtime Error

Solution code:
def get():
	p,w = map(int, raw_input().split(","))
	for i in range(W-w+1,-1,-1):
		if bag[i] > 0 and bag[i]+p > bag[i+w]:
			bag[i+w] = bag[i]+p
	else:
		if p > bag[w]: bag[w] = p
	return

c = 1
while True:
	W = int(raw_input())
	if W == 0: break
	bag = [0]*(W+1)
	N = int(raw_input())
	for i in range(N): get()
	w_all = max(bag)
	money = bag.index(w_all)
	print "Case {}:\n{}\n{}".format(c,w_all,money)
	c += 1