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:
# Aizu Problem 0042: A Thief
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def knapsack(n, v, w, W):
    #
    # 0/1 knapsack implementation
    #
    # Input:
    #    Values (stored in array v)
    #    Weights (stored in array w)
    #    Number of distinct items (n)
    #    Knapsack capacity (W)
    #
    m = [[0 for _ in range(W + 1)] for __ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(W + 1):
            if w[i - 1] > j:
                m[i][j] = m[i-1][j]
            else:
                m[i][j] = max(m[i-1][j], m[i-1][j-w[i - 1]] + v[i - 1])
    print(m)
    return m[N][W]

def total_value(items, max_weight):
    return  sum([x[2] for x in items]) if sum([x[1] for x in items]) < max_weight else 0
 
cache = {}
def solve(items, max_weight):
    if not items:
        return ()
    if (items,max_weight) not in cache:
        head = items[0]
        tail = items[1:]
        include = (head,) + solve(tail, max_weight - head[1])
        dont_include = solve(tail, max_weight)
        if total_value(include, max_weight) > total_value(dont_include, max_weight):
            answer = include
        else:
            answer = dont_include
        cache[(items,max_weight)] = answer
    return cache[(items,max_weight)]

case = 0
while True:
    cache = {}
    W = int(input())
    if W == 0:
        break
    N = int(input())
    items = []
    for n in range(N):
        a, b = [int(_) for _ in input().split(',')]
        items.append(("", b, a))
    items = tuple(items)
    solution = solve(items, W)
    case += 1
    print("Case %d:" % case)
    print(sum([x[2] for x in solution]))
    print(sum([x[1] for x in solution]))

Submission status: Wrong Answer

Solution code:
# Aizu Problem 0042: A Thief
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def knapsack(n, v, w, W):
    #
    # 0/1 knapsack implementation
    #
    # Input:
    #    Values (stored in array v)
    #    Weights (stored in array w)
    #    Number of distinct items (n)
    #    Knapsack capacity (W)
    #
    m = [[0 for _ in range(W + 1)] for __ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(W + 1):
            if w[i - 1] > j:
                m[i][j] = m[i-1][j]
            else:
                m[i][j] = max(m[i-1][j], m[i-1][j-w[i - 1]] + v[i - 1])
    print(m)
    return m[N][W]

def total_value(items, max_weight):
    return  sum([x[2] for x in items]) if sum([x[1] for x in items]) < max_weight else 0
 
cache = {}
def solve(items, max_weight):
    if not items:
        return ()
    if (items,max_weight) not in cache:
        head = items[0]
        tail = items[1:]
        include = (head,) + solve(tail, max_weight - head[1])
        dont_include = solve(tail, max_weight)
        if total_value(include, max_weight) > total_value(dont_include, max_weight):
            answer = include
        else:
            answer = dont_include
        cache[(items,max_weight)] = answer
    return cache[(items,max_weight)]

case = 0
while True:
    cache = {}
    W = int(input())
    if W == 0:
        break
    N = int(input())
    items = []
    for n in range(N):
        a, b = [int(_) for _ in input().split(',')]
        items.append(("", b, a))
    items = tuple(items)
    solution = solve(items, W)
    case += 1
    print("Case %d:" % case)
    print(total_value(solution, W))
    print(sum([x[1] for x in solution]))

Submission status: Wrong Answer

Solution code:
count=1
while True:
    vw=[[0,0]]
    W=int(input())
    if W==0:
        break
    n=int(input())
    for i in range(n):
        vw.append(list(map(int,input().split(','))))
    
    dp=[]
    weight=[]
    
    for _ in range(n+1):
        dp.append([0 for i in range(W+1)])
        weight.append([0 for i in range(W+1)])
    for i in range(1,n+1):
        for j in range(0,W-vw[i][1]+1):
            dp[i][j+vw[i][1]]=max(dp[i-1][j+vw[i][1]],dp[i-1][j]+vw[i][0])
            if dp[i][j+vw[i][1]]==dp[i-1][j]+vw[i][0]:
                weight[i][j+vw[i][1]]=weight[i-1][j]+vw[i][1]
            else:
                weight[i][j+vw[i][1]]=weight[i-1][j]
            
    print('Case '+'{}'.format(count)+':')
    print(dp[n][W])
    print(weight[n][W])
    count+=1

Submission status: Wrong Answer

Solution code:
count=1
while True:
    vw=[[0,0]]
    W=int(input())
    if W==0:
        break
    n=int(input())
    for i in range(n):
        vw.append(list(map(int,input().split(','))))
    
    dp=[]
    weight=[]
    
    for _ in range(n+1):
        dp.append([0 for i in range(W+1)])
        weight.append([0 for i in range(W+1)])
    for i in range(1,n+1):
        for j in range(0,W-vw[i][1]+1):
            dp[i][j+vw[i][1]]=max(dp[i-1][j+vw[i][1]],dp[i-1][j]+vw[i][0])
            
            if dp[i-1][j+vw[i][1]]==dp[i-1][j]+vw[i][0]:
                weight[i][j+vw[i][1]]=min(weight[i-1][j]+vw[i][1],weight[i-1][j])  
            elif dp[i][j+vw[i][1]]==dp[i-1][j]+vw[i][0]:
                weight[i][j+vw[i][1]]=weight[i-1][j]+vw[i][1]
            else:
                weight[i][j+vw[i][1]]=weight[i-1][j]
            
    print('Case '+'{}'.format(count)+':')
    print(dp[n][W])
    print(weight[n][W])
    count+=1

Submission status: Wrong Answer

Solution code:
count=1
while True:
    vw=[[0,0]]
    W=int(input())
    if W==0:
        break
    n=int(input())
    for i in range(n):
        vw.append(list(map(int,input().split(','))))
    
    dp=[]
    weight=[]
    
    for _ in range(n+1):
        dp.append([0 for i in range(W+1)])
        weight.append([0 for i in range(W+1)])
    for i in range(1,n+1):
        for j in range(0,W-vw[i][1]+1):
            dp[i][j+vw[i][1]]=max(dp[i-1][j+vw[i][1]],dp[i-1][j]+vw[i][0])
            
            if dp[i-1][j+vw[i][1]]==dp[i-1][j]+vw[i][0]:
                weight[i][j+vw[i][1]]=min(weight[i-1][j]+vw[i][1],weight[i-1][j+vw[i][1]])  
            elif dp[i][j+vw[i][1]]==dp[i-1][j]+vw[i][0]:
                weight[i][j+vw[i][1]]=weight[i-1][j]+vw[i][1]
            else:
                weight[i][j+vw[i][1]]=weight[i-1][j+vw[i][1]]
    print('Case '+'{}'.format(count)+':')
    print(dp[n][W])
    print(weight[n][W])
    count+=1

Submission status: Wrong Answer

Solution code:
import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = w_max
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w < w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case:",case)
    print(v_best)
    print(w_best)

Submission status: Wrong Answer

Solution code:
import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = 0
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w < w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case:",case)
    print(v_best)
    print(w_best)

Submission status: Wrong Answer

Solution code:
import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = 0
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w < w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case",case,":")
    print(v_best)
    print(w_best)

Submission status: Wrong Answer

Solution code:
import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = 0
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w < w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case ",case,":",sep="")
    print(v_best)
    print(w_best)

Submission status: Wrong Answer

Solution code:
"""
0-1ナップザック
dp[i][j]...i個目までの宝で重さjの時の価値の最大
wi = wlst[i]...i個目の重さ
vi = vlst[i]...i個目の価値
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - wi] + vi)  (wi <= j)
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])                          (wi >  j)
"""


def main():
  case = 0

  while True:
    w = int(input())
    if not w:
      break
  
    case += 1
  
    n = int(input())
  
    vlst = [0]
    wlst = [0]
  
    for _ in range(n):
      vin, win = map(int, input().split(","))
      vlst.append(vin)
      wlst.append(win)

    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
      vi, wi = vlst[i], wlst[i]
      dpi = dp[i]
      dpim = dp[i - 1]
      for j in range(1, w + 1):
        if j >= wlst[i]:
          dpi[j] = max(dpim[j], dpi[j - 1], dpim[j - wi] + vi)
        else:
          dpi[j] = max(dpi[j], dpi[j - 1])
  
    print("Case " + str(case) + ":")
    print(dp[n][w])

    for i in range(w, -1, -1):
      if dp[n][i] != dp[n][w]:
        print(i + 1)
        break

main()

Submission status: Wrong Answer

Solution code:
# AOJ 0042 A Thief
# Python3 2018.6.22 bal4u

MAX = 1003

for cno in range(1, 100):
	lim = int(input())
	if lim == 0: break
	print("Case ", cno, ":", sep='')
	N = int(input())
	vw = []
	for i in range(N):
		v, w = list(map(int, input().split(',')))
		vw.append((v, w))

	V = [[0 for j in range(MAX)] for i in range(2)]
	W = [[0 for j in range(MAX)] for i in range(2)]		
	k1, k2 = 0, 1
	for i in range(N):
		for j in range(lim):
			if vw[i][1] > j:
				V[k2][j] = V[k1][j]
				W[k2][j] = W[k1][j]
			else:
				d = j - vw[i][1]
				if V[k1][d] + vw[i][0] >= V[k1][j]:
					V[k2][j] = V[k1][d] + vw[i][0]
					W[k2][j] = W[k1][d] + vw[i][1]
				else:
					V[k2][j] = V[k1][j]
					W[k2][j] = W[k1][j];
		k1, k2 = k2, 1-k1
	print(V[k1][lim-1], W[k1][lim-1], sep='\n');

Submission status: Wrong Answer

Solution code:

import sys


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


def solv(treasures, w_limit):
    treasures.sort(cmp_treasure)
    swag = reduce(take_treasure(w_limit), treasures, (0, 0))
    return swag


def cmp_treasure(a, b):
    if a.value == b.value:
        return cmp(a.weight, b.weight)
    else:
        return cmp(b.value, a.value)


def take_treasure(w):
    def func(acc, t):
        if acc[1] + t.weight <= w:
            value = acc[0] + t.value
            weight = acc[1] + t.weight
            return (value, weight)
        else:
            return acc
    return func


case = 0

while True:
    w_limit = int(sys.stdin.readline())
    case += 1
    if w_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, w_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight

Submission status: Wrong Answer

Solution code:

import sys


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

    def unit_value(self):
        return self.value / self.weight


def solv(treasures, w_limit):
#    treasures.sort(cmp_treasure)
    treasures.sort(lambda t1, t2: cmp(t2.unit_value, t1.unit_value))
    swag = reduce(take_treasure(w_limit), treasures, (0, 0))
    return swag


def cmp_treasure(a, b):
    if a.value == b.value:
        return cmp(a.weight, b.weight)
    else:
        return cmp(b.value, a.value)


def take_treasure(w):
    def func(acc, t):
        if acc[1] + t.weight <= w:
            value = acc[0] + t.value
            weight = acc[1] + t.weight
            return (value, weight)
        else:
            return acc
    return func


case = 0

while True:
    w_limit = int(sys.stdin.readline())
    case += 1
    if w_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, w_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight

Submission status: Wrong Answer

Solution code:

import sys
import itertools


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



def solv(treasures, w_limit):
    treasures.sort(lambda a, b: cmp(b.value, a.value))
    tvw = (0, 0)
    for ts in t_combinations(treasures):
        w = t_sum_weight(ts)
        if w <= w_limit:
            v = t_sum_value(ts)
            if tvw[0] < v:
                 tvw = (v, w)
            elif tvw[0] == v:
                 if w < tvw[1]:
                     tvw = (v, w)
    return tvw


def t_combinations(t):
    l = len(t)
    for x in range(l+1, 1, -1):
        for y in itertools.combinations(t, x):
            yield y


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

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

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

Submission status: Wrong Answer

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().strip())
    if not W:
        break

    N = int(stdin.readline().strip())
    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))

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

Submission status: Wrong Answer

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().strip())
    if not W:
        break

    N = int(stdin.readline().strip())
    data = []
    for _ in range(N):
        data.append([int(s) for s in stdin.readline().strip().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))

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

Submission status: Wrong Answer

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().strip())
    if not W:
        break

    N = int(stdin.readline().strip())
    data = []
    for _ in range(N):
        data.append([int(s) for s in stdin.readline().strip().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-1:
                total.append((tv, tw))

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

Submission status: Wrong Answer

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):
    WEIGHT = int(stdin.readline().strip())
    if not WEIGHT:
        break

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

    total = []
    for i in range(1, NUM+1):
        for cmb in combinations(data, i):
            tw = sum(w for v, w in cmb)
            if tw < WEIGHT:
                total.append((sum(v for v, w in cmb), tw))

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

Submission status: Wrong Answer

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):
    WEIGHT = int(stdin.readline().strip())
    if not WEIGHT:
        break

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

    total = []
    for i in range(1, NUM+1):
        for cmb in combinations(data, i):
            tw = sum(w for v, w in cmb)
            if WEIGHT > tw:
                total.append((sum(v for v, w in cmb), tw))

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

Submission status: Wrong Answer

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):
    WEIGHT = int(stdin.readline().strip())
    if not WEIGHT:
        break

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

    total = []
    for i in range(1, NUM+1):
        for cmb in combinations(data, i):
            tw = sum(w for v, w in cmb)
            if WEIGHT > tw:
                total.append((sum(v for v, w in cmb), tw))
    print(total)
    if len(total):
        tv, tw = max(total, key=lambda(tv, tw): (tv, -tw))
    else:
        tv, tw = 0, 0
    print('Case {}:\n{}\n{}'.format(case, tv, tw))

Submission status: Wrong Answer

Solution code:
count =0
while True:
    W = input()
    if (W==0): break
    work={0:0}
    count +=1
    N = input()
    for i in range(N):
        p,w = input()
        for w0 in work.keys():
            w1 = w0+w
            p1 = work[w0]+p
            if w1>W or (work.has_key(w1) and work[w1]>=p1): continue
            work[w1] = p1
    m = max(work.values())
    tmp = work.values().index(m)
    n = work.keys()[tmp]
    print "Case %d:" %(count)
    print m
    print n

Submission status: Wrong Answer

Solution code:
count =0
while True:
    W = input()
    if W==0: break
    work=[0]*1001
    count +=1
    N = input()
    m=0
    n=0
    for i in range(N):
        p,w = input()
        for w0 in range(W+1)[::-1]:
            p0 = work[w0]
            if w0>0 and p0==0: continue
            w1 = w0+w
            p1 = p0+p
            if w1<W and work[w1]<p1:
                work[w1] = p1
                if m<p1:
                    m=p1
                    n=w1
    print "Case {}:".format(count)
    print m
    print n

Submission status: Wrong Answer

Solution code:
def f():
    global dt
    p,w = input()
    R = range(W+1)[::-1]
    for w0 in R[:-1]:
        w1,p1 = w0+w,dt[w0]+p
        if w1<=W and dt[w1]<p1: dt[w1]=p1
    dt[w]=dt[0]+p
    return

c = 0
while 1:
    W = input()
    if W==0: break
    dt = [0]*1001
    c += 1
    N = input()
    for i in range(N): f()
    m = max(dt)
    n = dt.index(m)
    print "Case {}:".format(c)
    print m
    print n

Submission status: Wrong Answer

Solution code:
def mlist(n, *args, **keys):
    if args:
        return [mlist(*args, **keys) for i in range(n)]
    else:
        return [keys.get('default')] * n

while True:
    w = int(raw_input())
    if w == 0: break
    n = int(raw_input())
    a, b = zip(*[map(int, raw_input().split(',')) for i in range(n)])
    c = mlist(1010, 1010)
    c[0][0] = 0
    for i in range(n):
        for j in range(w + 1):
            if c[i][j] is None: continue
            c[i + 1][j] = max(c[i + 1][j], c[i][j])
            if j + b[i] <= w:
                c[i + 1][j + b[i]] = max(c[i + 1][j + b[i]], c[i][j] + a[i])
    mx = max(c[n])
    print mx
    print c[n].index(mx)

Submission status: Time Limit Exceeded

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 cp == mp and mw > cw: mw = cw
    if w >= cw 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: Time Limit Exceeded

Solution code:
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: Time Limit Exceeded

Solution code:
memo = {}


def furoshiki(i, w_limit):
    global memo, treasures

    if not i or not w_limit:
        return (0, 0)

    if (i, w_limit) in memo:
        return memo[(i, w_limit)]

    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)
    memo.clear()
    case += 1

Submission status: Time Limit Exceeded

Solution code:
import re
def solve(w,v):
    n = len(v)
    val0 = 0
    wgt0 = 0
    for i in range(1,2**n):
        s = bin(i)
        s1 = '0'*n + re.sub(r'0b', '', s)
        t = list(map(int, list(s1[-n:])))
        val = wgt = 0
         
        for i in range(n):
            if t[i]==1:
                val += v[i][0]  
                wgt += v[i][1]  
        if wgt > w:
            continue
        if val > val0 or (val==val0 and wgt<wgt0):
            val0 = val
            wgt0 = wgt
    return(val0,wgt0)

case=0
while True:
    case += 1
    f = []
    wlim = int(input().strip())
    if wlim==0:
        break
    n = int(input().strip())
    for i in range(n):
        v,w = map(int,input().strip().split(','))
        f.append((v,w))
    
    val,wgt = solve(wlim,f)
    
    print('Case %d:' % case)
    print(val)
    print(wgt)

Submission status: Time Limit Exceeded

Solution code:
import re
def solve(w,v):
    n = len(v)
    val0 = 0
    wgt0 = 0
    for i in range(1,2**n):
        s = bin(i)
        s1 = '0'*n + re.sub(r'0b', '', s)
        t = list(map(int, list(s1[-n:])))
        val = wgt = 0
         
        for i in range(n):
            if t[i]==1:
                val += v[i][0]  
                wgt += v[i][1]  
                if wgt > w:
                    break
        if wgt > w:
            continue
        if val > val0 or (val==val0 and wgt<wgt0):
            val0 = val
            wgt0 = wgt
    return(val0,wgt0)

case=0
while True:
    case += 1
    f = []
    wlim = int(input().strip())
    if wlim==0:
        break
    n = int(input().strip())
    for i in range(n):
        v,w = map(int,input().strip().split(','))
        f.append((v,w))
    
    val,wgt = solve(wlim,f)
    
    print('Case %d:' % case)
    print(val)
    print(wgt)

Submission status: Time Limit Exceeded

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

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)

    v, w = ns(vs, ws, 0, W)
    print('Case ' + str(casenum) + ':')
    print(v)
    print(w)
    casenum += 1

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = 0
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w <= w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case ",case,":",sep="")
    print(v_best)
    print(w_best)