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: Wrong Answer

Solution code:
from sys import stdin

case = 0
while(True):
    case += 1
    W = int(stdin.readline())
    if not W: break
    print("Case %d"%case)
    N = int(stdin.readline())
    v = [0] * N
    w = [0] * N
    dp = [[0]*(W + 1) for _ in range(N + 1)]

    for k in range(N):
        v[k], w[k] = map(int, stdin.readline().split(","))
    for i in range(N-1,-1,-1):
        for j in range(W+1):
            if j < w[i]:
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i])
    print(dp[0][W])
    for i in range(W+1):
        if dp[0][i] == dp[0][W]: print(i); break

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import sys
import copy

def main():
    line = sys.stdin.readline()
    i = 1
    #case
    while int(line) != 0:
        analy(line, i)
        i = i + 1
        line = sys.stdin.readline()

def analy(line, case):
    #整列
    weight = int(line)
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split(",")]
        #価値、重さ
        data.append(b)
    #軽い順に並び替える,同じ重さなら価値の低い順になってる
    data.sort(key=lambda x:(x[1], x[0]))
    #重さ重複を削除
    i = 0
    while i < len(data)-1:
        if data[i][1] == data[i+1][1]:
            del data[i]
        else:
            i = i + 1
    num = len(data)
    yar(data, weight, num, case)

def yar(data, weight, num ,case):
    # 価値、重さ
    tmp = [[0,0]]
    kek = []
    calc(tmp, data, weight, kek, num)
    kek.sort(key=lambda x:(x[0], -x[1]))
    kek.reverse()
    print("Case " + str(case) + ':')
    print(kek[0][0])
    print(kek[0][1])

def calc(tmp, data, weight, kek, num):
    for j in range(num):
        a = len(tmp)
        for i in range(a):
        #とりあえず全てにおなじdataのやつを足してくわえる
            tlis = copy.deepcopy(tmp[i])
            tlis[0] = data[j][0] + tlis[0]
            tlis[1] = data[j][1] + tlis[1]
            if tlis[1] <= weight:
                tmp.append(tlis)
            else:
            #軽い順に並べてるのでそれがダメだと残りの要素すべて×、その後も×になる
                for k in range(i,a):
                    kek.append(tmp[i])
                    del tmp[i]
                break
        #軽い順に並び替える,同じ重さなら価値の低い順になってる
        tmp.sort(key=lambda x:(x[1],x[0]))      
    for j in range(len(tmp)):
        kek.append(tmp[j])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import sys
import copy

def main():
    line = sys.stdin.readline()
    i = 1
    #case
    while int(line) != 0:
        analy(line, i)
        i = i + 1
        line = sys.stdin.readline()

def analy(line, case):
    weight = int(line)
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split(",")]
        data.append(b)
    data.sort(key=lambda x:(x[1], x[0]))
    i = 0
    while i < len(data)-1:
        if data[i][1] == data[i+1][1]:
            del data[i]
        else:
            i = i + 1
    num = len(data)
    yar(data, weight, num, case)

def yar(data, weight, num ,case):
    tmp = [[0,0]]
    kek = []
    calc(tmp, data, weight, kek, num)
    kek.sort(key=lambda x:(x[0], -x[1]))
    kek.reverse()
    print("Case " + str(case) + ':')
    print(kek[0][0])
    print(kek[0][1])

def calc(tmp, data, weight, kek, num):
    for j in range(num):
        a = len(tmp)
        for i in range(a):
            tlis = copy.deepcopy(tmp[i])
            tlis[0] = data[j][0] + tlis[0]
            tlis[1] = data[j][1] + tlis[1]
            if tlis[1] <= weight:
                tmp.append(tlis)
            else:
                for k in range(i,a):
                    kek.append(tmp[i])
                    del tmp[i]
                break
        tmp.sort(key=lambda x:(x[1],x[0]))
        i = 0
        while i < len(tmp)-1:
            if tmp[i][1] == tmp[i+1][1]:
                del tmp[i]
            else:
                i = i + 1
    for j in range(len(tmp)):
        kek.append(tmp[j])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
caseN = 0
while True:
    caseN += 1
    W = int(input())
    if W == 0: break
    N = int(input())
    tr = [list(map(int, input().split(','))) for _ in range(N)]
    dp = [[0 for x in range(W+1)] for y in range(N+1)]
    for x in range(N):
        for y in range(W+1):
            if y >= tr[x][1]:
                dp[x+1][y] = max(dp[x+1][y], dp[x][y-tr[x][1]]+tr[x][0])
    sum_weight = 0
    sum_value = 0
    for x in range(W+1):
        if dp[N][x] > sum_value:
            sum_weight = x
            sum_value = dp[N][x]
    print("Case ", caseN, ":", sep='')
    print(sum_value, sum_weight, sep='\n')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from itertools import *
from sys import *

def solve(n,w):
  lp,lw = [],[]
  for i in xrange(n):
    s = map(int, raw_input().split(","))
    lp.append(s[0])
    lw.append(s[1])
  mp = mw = 0
  for e in product([0,1],repeat=n):
    cw = sum([ lw[i] for i in range(len(e)) if e[i] ])
    cp = sum([ lp[i] for i in range(len(e)) if e[i] ])
    if cw < w and cp > mp : mp = cp ; mw = cw
  print mp
  print mw

case = 0
while True:
  case += 1
  w = int(raw_input())
  if w == 0: break
  n = int(raw_input())
  print "Case %d:" % (case)
  solve(n,w)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve(c, W, vl):
    dp = [0] * W
    for v in vl:
        for i in reversed(xrange(v[1], W)):
            dp[i] = max(dp[i - v[1]] + v[0], dp[i])
    print "Case {}:".format(c)
    print dp[W-1]
    print len(filter(lambda x:x < dp[W-1], dp))

c = 1
while 1:
    W = int(raw_input())
    if not W: break
    N = int(raw_input())
    solve(c, W, [map(int, raw_input().split(",")) for _ in xrange(N)])
    c += 1

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve(c, W, vl):
    dp = [0] * W
    for v in vl:
        for i in reversed(xrange(v[1], W)):
            dp[i] = max(dp[i - v[1]] + v[0], dp[i])
    print "Case {}:\n{}\n{}".format(c,dp[W-1],len(filter(lambda x: x<dp[W-1], dp)))

c = 1
while 1:
    W = int(raw_input())
    if not W: break
    N = int(raw_input())
    solve(c, W, [map(int, raw_input().split(",")) for _ in xrange(N)])
    c += 1

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve(c, W, vl):
    dp = [0] * W
    for v in vl:
        for i in reversed(xrange(v[1], W)):
            dp[i] = max(dp[i - v[1]] + v[0], dp[i])
    print "Case {}:\n{}\n{}".format(c, dp[W-1], dp.index(dp[W-1]))

c = 1
while 1:
    W = int(raw_input())
    if not W: break
    N = int(raw_input())
    solve(c, W, [map(int, raw_input().split(",")) for _ in xrange(N)])
    c += 1

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve(c, W, vl):
    dp = [0] * W
    for v in vl:
        for i in xrange(W-1, v[1]-1, -1):
            dp[i] = max(dp[i - v[1]] + v[0], dp[i])
    print "Case {}:\n{}\n{}".format(c, dp[W-1], dp.index(dp[W-1]))

c = 1
while 1:
    W = int(raw_input())
    if not W: break
    N = int(raw_input())
    solve(c, W, [map(int, raw_input().split(",")) for _ in xrange(N)])
    c += 1

Submission status: Wrong Answer

Solution code:
while True:
    try:
        case=0
        while True:
            case+=1
            weight=input()
            if weight==0:
                break
            N=input()
            data=[[0 for i in range(2)] for j in range(N)]
            for i in range(N):
                data[i][0],data[i][1]=map(int,raw_input().split(","))
            table=[[-1 for i in range(weight+1)] for j in range(N)]
            for i in range(N):
                table[i][0]=0
            table[0][data[0][1]]=data[0][0]
            for i in range(0,N-1):
                for j in range(weight+1):
                    if table[i][j]!=-1 and j+data[i+1][1] <= weight:
                        table[i+1][j+data[i+1][1]]=table[i][j]+data[i+1][0]
            sum=max(table[N-1])
            print "Case "+str(case)+":"
            print sum
            print table[N-1].index(sum)
    except:
        break

Submission status: Wrong Answer

Solution code:
while True:
    try:
        case=0
        while True:
            case+=1
            weight=input()
            if weight==0:
                break
            N=input()
            if N==0:
                print "Case "+str(case)+":"
                print 0
                print 0
                break
            data=[[0 for i in range(2)] for j in range(N)]
            for i in range(N):
                data[i][0],data[i][1]=map(int,raw_input().split(","))
            table=[[-1 for i in range(weight+1)] for j in range(N)]
            for i in range(N):
                table[i][0]=0
            table[0][data[0][1]]=data[0][0]
            for i in range(0,N-1):
                for j in range(weight+1):
                    if table[i][j]!=-1 and j+data[i+1][1] <= weight:
                        table[i+1][j+data[i+1][1]]=table[i][j]+data[i+1][0]
            sum=max(table[N-1])
            print "Case "+str(case)+":"
            print sum
            print table[N-1].index(sum)
    except:
        break

Submission status: Wrong Answer

Solution code:
while True:
    try:
        case=0
        while True:
            case+=1
            weight=input()
            if weight==0:
                break
            N=input()
            data=[[0 for i in range(2)] for j in range(N)]
            for i in range(N):
                data[i][0],data[i][1]=map(int,raw_input().split(","))
            table=[[-1 for i in range(weight+1)] for j in range(N)]
            for i in range(N):
                table[i][0]=0
            table[0][data[0][1]]=data[0][0]
            for i in range(0,N-1):
                for j in range(weight+1):
                    if table[i][j]!=-1 and j+data[i+1][1] <= weight and\
                       table[i][j+data[i+1][1]] < table[i][j]+data[i+1][0]:
                        table[i+1][j+data[i+1][1]]=table[i][j]+data[i+1][0]
            sum=max(table[N-1])
            print "Case "+str(case)+":"
            print sum
            print table[N-1].index(sum)
    except:
        break

Submission status: Wrong Answer

Solution code:
def asmr(lis):
    global m_v, m_w
    for i, v_w in enumerate(lis):
        if sum(w) + v_w[1] <= W:
            v.append(v_w[0])
            w.append(v_w[1])
            asmr(lis[i+1:])
            del v[-1]
            del w[-1]
        else:
            if (m_v == None) or (m_v < sum(v)):
                m_v = sum(v)
                m_w = sum(w)
            elif m_v == sum(v):
                if m_w > sum(w):
                    m_w = sum(w)
    else:
        if (m_v == None) or (m_v < sum(v)):
            m_v = sum(v)
            m_w = sum(w)
        elif m_v == sum(v):
            if m_w > sum(w):
                m_w = sum(w) 

while True:
    W = int(raw_input())
    if W == 0: break
    N = int(raw_input())
    lis = [map(int, raw_input().split(',')) for i in range(N)]
    lis = sorted(lis, key=lambda x: x[0], reverse=True)
    m_v = None
    m_w = None
    v = []
    w = []
    asmr(lis)
    print m_v
    print m_w

Submission status: Wrong Answer

Solution code:
# ナップサック問題を python で解く
case = 0
while True:
    case += 1
    w = int(input())
    if w == 0:
        break
    n = int(input())
    item = []
    for i in range(n):
        item.append(tuple(map(int, input().split(","))))

    dp = [ [0 for j in range(w + 1)] for i in range(n + 1) ]
    for i in range(n):
        for j in range(w + 1):
            value  = item[i][0]
            weight = item[i][1]
            # dp[i][j] : 0..i番目の荷物、重さ j 以下の最大の価値
            if j - weight >= 0 and dp[i+1][j - weight] == dp[i][j - weight]:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j - weight] + value)
            else:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-1])

    for j in range(w + 1):
        if dp[n][j] == dp[n][w]:
            max_w = j
            break

    print("Case {0}".format(case))
    print(dp[n][w])
    print(max_w)

Submission status: Wrong Answer

Solution code:
# ナップサック問題を python で解く
case = 0
while True:
    case += 1
    w = int(input())
    if w == 0:
        break
    n = int(input())
    item = []
    for i in range(n):
        item.append(tuple(map(int, input().split(","))))

    dp = [ [0 for j in range(w + 1)] for i in range(n + 1) ]
    for i in range(n):
        for j in range(w + 1):
            value  = item[i][0]
            weight = item[i][1]
            # dp[i][j] : 0..i番目の荷物、重さ j 以下の最大の価値
            if j - weight >= 0 and dp[i+1][j - weight] == dp[i][j - weight]:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j - weight] + value)
            else:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-1])

    for j in range(w + 1):
        if dp[n][j] == dp[n][w]:
            max_w = j
            break

    print("Case {0}:".format(case))
    print(dp[n][w])
    print(max_w)

Submission status: Wrong Answer

Solution code:
def memoize(f):
    memo = {}

    def main(*args):
        if args in memo:
            return memo[args]
        result = memo[args] = f(*args)
        return result

    return main


@memoize
def furoshiki(i, w_limit):
    global treasures
    if not i or not w_limit:
        return (0, 0)

    v, w = treasures[i - 1]
    not_stole = furoshiki(i - 1, w_limit)
    if w_limit < w:
        return not_stole
    stole_v_total, stole_w_total = furoshiki(i - 1, w_limit - w)
    stole_v_total += v
    stole_w_total -= w
    return max(not_stole, (stole_v_total, stole_w_total))


case = 1
while True:
    w = int(input())
    if not w:
        break
    n = int(input())
    treasures = [None] * n
    for i in range(n):
        treasures[i] = tuple(map(int, input().split(',')))

    total_v, total_w = furoshiki(n, w)
    print('Case {}:'.format(case))
    print(total_v)
    print(-total_w)
    case += 1

Submission status: Wrong Answer

Solution code:
import sys

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

def rec_dp(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    res = 0
    if i == n:
        res == 0
    elif j < item[i].weight:
        res = rec_dp(i+1, j)
    else:
        res = max(rec_dp(i+1, j), rec_dp(i+1, j-item[i].weight)+item[i].value)
    dp[i][j] = res
    return res

k = 0
while True:
    W = int(raw_input())
    if not W:
        break
    k += 1
    n = int(raw_input())
    item = []
    dp = [[-1 for j in range(W+1)] for i in range(n+1)]
    for i in range(n):
        v, w = map(int, raw_input().split(','))
        item.append(Item_class(v, w))
    item.append(Item_class(0, 0))
    v_max = rec_dp(0, W)
    print "Case %d:" %(k)
    print v_max
    w_sum = 0
    for i in range(1, n+1):
        if dp[i][W] != v_max:
            w_sum += item[i-1].weight
    print w_sum

Submission status: Wrong Answer

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

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(v, w)

Submission status: Wrong Answer

Solution code:
while True:
    cnt = 0
    cnt += 1
    maxweight = int(input())
    if maxweight == 0:
        break
    length = int(input())
    tresure = []
    dp = [[0 for n in range(length+1)] for m in range(maxweight + 1)]
    answeight = 0
    ansvalue = 0
    for l in range(length):
        v,w = (int(n) for n in input().split(","))
        tresure.append([v,w])
    for outer in range(length + 1):
        if outer == 0:
            continue
        weight = tresure[outer-1][1]
        value = tresure[outer-1][0]
        dp[weight][outer] = max(dp[weight][outer],value)
        for inner in range(maxweight + 1):
            if dp[inner][outer - 1] != 0:
                beforevalue = dp[inner][outer - 1]
                beforeweight = inner
                dp[inner][outer]  = max(beforevalue,dp[inner][outer])
                if beforeweight + weight <= maxweight:
                    nowvalue = dp[beforeweight + weight][outer]
                    dp[beforeweight + weight][outer] = max(nowvalue,beforevalue+value)
    #print(dp)
    for a in range(maxweight+1):
        #print(dp[a][length])
        if ansvalue < dp[a][length]:
            ansvalue = dp[a][length]
            answeight = a
    print("Case {0}:".format(cnt))
    print(ansvalue)
    print(answeight)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
case = 1

while 1:
	W = int(input())
	if W == 0:
		break
	N = int(input())

	v = []
	w = []

	for _ in range(N):
		v_, w_ = map(int,input().split(","))
		v.append(v_)
		w.append(w_)

	dp = [[0 for _ in range(W)] for _ in range(N)]
	for i in range(w[0],W):
		dp[0][i] = v[0]

	for i in range(1, N):
		for j in range(W):
			if j - w[i] < 0:
				dp[i][j] = dp[i-1][j]
			else:
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])

	res = dp[N-1][W-1]
	minw = min([i for i in range(W) if dp[N-1][i] == res])

	print("Case "+str(case)+":")
	print(res)
	print(minw)
	case += 1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math
import itertools

case = 1
for s in sys.stdin:
    W = int(s)
    if W == 0:
        break

    N = int(input())
    values = []
    weights = []
    for i in range(N):
        v, w = map(int, input().split(','))
        values.append(v)
        weights.append(w)

    max_value = 0
    max_value_weight = 0
    for use_flags in itertools.product([0, 1], repeat=len(weights)):

        sum_value = 0
        sum_weight = 0
        for i, use_flag in enumerate(use_flags):
            if use_flag == 1:
                sum_value += values[i]
                sum_weight += weights[i]
        if sum_weight <= W and sum_value > max_value:
            max_value = sum_value
            max_value_weight = sum_weight

    case += 1
    print('Case {}:'.format(case))
    print(max_value)
    print(max_value_weight)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
count = 1

while 1:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    data =[]
    dp = [[[-1,0]for i in range(W+1)]for i in range(N+1)]

    for i in range(N):
        data.append(input().split(","))

    for i in range(W+1):
        dp[N][i][0] = 0
    for i in reversed(range(N)):
        for capa in range(W):
            if int(data[i][1]) >  capa:
                dp[i][capa][0] = dp[i+1][capa][0]
                dp[i][capa][1] = dp[i+1][capa][1]
            else:
                dp[i][capa][0] = max(int(data[i][0])+dp[i+1][capa-int(data[i][1])][0],dp[i+1][capa][0])
                dp[i][capa][1] = dp[i+1][capa][1]
                if dp[i][capa][0] != dp[i+1][capa][0]:
                    dp[i][capa][1] += int(data[i][1])

    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
    count += 1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
count = 1

while 1:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    data =[]
    dp = [[[-1,0]for i in range(W+1)]for i in range(N+1)]

    for i in range(N):
        data.append(input().split(","))

    for i in range(W+1):
        dp[N][i][0] = 0
    for i in reversed(range(N)):
        for capa in range(W):
            if int(data[i][1]) >  capa:
                dp[i][capa][0] = dp[i+1][capa][0]
                dp[i][capa][1] = dp[i+1][capa][1]
            else:
                dp[i][capa][0] = max(int(data[i][0])+dp[i+1][capa-int(data[i][1])][0],dp[i+1][capa][0])
                dp[i][capa][1] = dp[i+1][capa][1]
                if dp[i][capa][0] != dp[i+1][capa][0]:
                    dp[i][capa][1] += int(data[i][1])

    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
    count += 1

Submission status: Wrong Answer

Solution code:
# coding: utf-8

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
count = 1

while 1:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    data =[]
    dp = [[[-1,0]for i in range(W+1)]for i in range(N+1)]
    for i in range(N):
        data.append(input().split(","))

    for i in range(W+1):
        dp[N][i][0] = 0
    for i in reversed(range(N)):
        for capa in range(W+1):
            if int(data[i][1]) >  capa:
                dp[i][capa][0] = dp[i+1][capa][0]
                dp[i][capa][1] = dp[i+1][capa][1]
            else:
                dp[i][capa][0] = max(int(data[i][0])+dp[i+1][capa-int(data[i][1])][0],dp[i+1][capa][0])
                dp[i][capa][1] = dp[i+1][capa][1]
                if dp[i][capa][0] != dp[i+1][capa][0]:
                    dp[i][capa][1] += int(data[i][1])
    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
    print(dp)
    count += 1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
count = 1

while 1:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    data =[]
    dp = [[[-1,0]for i in range(W+1)]for i in range(N+1)]
    for i in range(N):
        data.append(input().split(","))

    for i in range(W+1):
        dp[N][i][0] = 0
    for i in reversed(range(N)):
        for capa in range(W+1):
            if int(data[i][1]) >  capa:
                dp[i][capa][0] = dp[i+1][capa][0]
                dp[i][capa][1] = dp[i+1][capa][1]
            else:
                dp[i][capa][0] = max(int(data[i][0])+dp[i+1][capa-int(data[i][1])][0],dp[i+1][capa][0])
                dp[i][capa][1] = dp[i+1][capa][1]
                if dp[i][capa][0] != dp[i+1][capa][0]:
                    dp[i][capa][1] += int(data[i][1])
    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
    count += 1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
count = 1

while 1:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    data =[]
    dp = [[[-1,0]for i in range(W+1)]for i in range(N+1)]
    for i in range(N):
        data.append(input().split(","))

    for i in range(W+1):
        dp[N][i][0] = 0
    for i in reversed(range(N)):
        for capa in range(W+1):
            if int(data[i][1]) > capa:
                dp[i][capa][0] = dp[i+1][capa][0]
                dp[i][capa][1] = dp[i+1][capa][1]
            else:
                dp[i][capa][0] = max(int(data[i][0])+dp[i+1][capa-int(data[i][1])][0],dp[i+1][capa][0])
                dp[i][capa][1] = capa
    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
    count += 1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
count = 1

while 1:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    data =[]
    dp = [[[-1,0]for i in range(W+1)]for i in range(N+1)]
    for i in range(N):
        data.append(input().split(","))

    for i in range(W+1):
        dp[N][i][0] = 0
    for i in reversed(range(N)):
        for capa in range(W+1):
            if int(data[i][1]) > capa:
                dp[i][capa][0] = dp[i+1][capa][0]
                dp[i][capa][1] = dp[i+1][capa][1]
            else:
                dp[i][capa][0] = max(int(data[i][0])+dp[i+1][capa-int(data[i][1])][0],dp[i+1][capa][0])
                dp[i][capa][1] = capa
               # if dp[i][capa][0] != dp[i+1][capa][0]:
                #    dp[i][capa][1] -= int(data[i][1])
    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
    #print(dp)
    count += 1

Submission status: Wrong Answer

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: Wrong Answer

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: Wrong Answer

Solution code:
c = 0
while True:
  W = int(input())
  if W == 0:
    break
  c += 1
  N = int(input())

  vl = [0]
  wl = [0]
  max_w = 0
  max_v = 0
  for i in range(N):
    [v,w] = list(map(int,input().split(",")))
    vl.append(v)
    wl.append(w)
  dp = [[0 for i in range(W+1)] for j in range(N+1)]
  for i in range(N+1):
    for j in range(W+1):
      if i == 0 or j == 0:
        dp[i][j] = 0
      else:
        if wl[i] <= j:
          dp[i][j] = max(dp[i-1][j-wl[i]] + vl[i], dp[i-1][j])
          if dp[i][j] > max_v:
            max_v = dp[i][j]
            max_w = j - 1
        else:
          dp[i][j] = dp[i-1][j]
  print("Case "+str(c)+":")
  print(max_v)
  print(max_w)

Submission status: Wrong Answer

Solution code:
C_num = 1
while True:
    Nap = []
    W = int(input())

    if W == 0:
        break
    N = int(input())
    for i in range(N):
        v,w = map(int,input().split(","))
        Nap.append([v,w])
    DP = [[0 for j in range(W + 1)] for i in range(N + 1)]
    for i in range(1,N+1):
            for j in range(W+1):
                if j - Nap[i-1][1] >= 0:
                    DP[i][j] = max(DP[i-1][j],DP[i - 1][j - Nap[i - 1][1]] + Nap[i - 1][0])
                else:
                    DP[i][j] = DP[i-1][j]
    omo = DP[N].index(DP[N][W])
    print("Case ",C_num,":",sep = "",end = "\n")
    print(DP[N][W])
    print(omo)

Submission status: Wrong Answer

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