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

Solution code:

import sys
import itertools


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



def solv(treasures, w_limit):
    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(1, l+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: Time Limit Exceeded

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, 0, -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: Time Limit Exceeded

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 xrange(N):
        data.append([int(s) for s in stdin.readline().strip().split(',')])

    value, weight = 0, W
    for i in xrange(1, N+1):
        for cmb in combinations(data, i):
            tv, tw = 0, 0
            for v, w in cmb:
                tv += v
                tw += w
            if W >= tw and (tv > value) or (tv == value and tw < weight):
                value, weight = tv, tw

    print('Case {}:\n{}\n{}'.format(case, value, weight))

Submission status: Time Limit Exceeded

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 xrange(N):
        data.append([int(s) for s in stdin.readline().strip().split(',')])
    data.sort(key=lambda (v,w): w)

    value, weight = 0, W
    for i in xrange(1, N+1):
        for cmb in combinations(data, i):
            tv, tw = 0, 0
            for v, w in cmb:
                tv += v
                tw += w
            if W < tw:
                break
            if W >= tw and (tv > value) or (tv == value and tw < weight):
                value, weight = tv, tw

    print('Case {}:\n{}\n{}'.format(case, value, weight))

Submission status: Memory Limit Exceeded

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: Memory Limit Exceeded

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))
    
    result = [0, 0]
    for _ in range(1, number+1) :
        temp1 = [sum(_2) for _2 in list(combinations(value, _))]
        temp2 = [sum(_2) for _2 in list(combinations(weight, _))]
        for _2 in range(len(temp1)) :
            if (result[0] < temp1[_2] and temp2[_2] <= limit) or (result[0] == temp1[_2] and temp2[_2] < result[1]) : result = temp1[_2], temp2[_2]
    print('Case {}:'.format(case))
    print(result[0])
    print(result[1])

Submission status: Memory Limit Exceeded

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

Submission status: Memory Limit Exceeded

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))
    
    result = [0, 0]
    for _ in range(1, number+1) :
        for a, b in zip(list(combinations(value, _)), list(combinations(weight, _))) :
            if (result[0] < sum(a) and sum(b) <= limit) or (result[0] == sum(a) and sum(b) < result[1]) :
                result = sum(a), sum(b)
    print('Case {}:'.format(case))
    print(result[0])
    print(result[1])

Submission status: Memory Limit Exceeded

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 (t_sum_value(ts2[0]), t_sum_weight(ts2[0]))
    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: Memory Limit Exceeded

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):
            tv, tw = 0, 0
            for value, weight in cmb:
                tv += value
                tw += weight
            if WEIGHT >= tw:
                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: Memory Limit Exceeded

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 xrange(NUM):
        data.append([int(s) for s in stdin.readline().strip().split(',')])

    total = []
    for i in xrange(1, NUM+1):
        for cmb in combinations(data, i):
            tv, tw = 0, 0
            for value, weight in cmb:
                tv += value
                tw += weight
            if WEIGHT >= tw:
                total.append((tv, tw))
        if len(total):
            total = [max(total, key=lambda(tv, tw): (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))
    del data
    del total

Submission status: Accepted

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: Accepted

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 x in range(N):
        for y in range(W,tr[x][1]-1,-1):
            dp[y] = max(dp[y], dp[y-tr[x][1]] + tr[x][0])
    sum_weight = 0
    sum_value = 0
    ind = N%2
    for x in range(W+1):
        if dp[x] > sum_value:
            sum_weight = x
            sum_value = dp[x]
    print("Case ", caseN, ":", sep='')
    print(sum_value)
    print(sum_weight)

Submission status: Accepted

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])
  c = [-1]*(w+1)
  c[0] = 0
  for i in xrange(n):
    for j in reversed(xrange(w)):
      if c[j] == -1 or j+lw[i] > w : continue
      c[j+lw[i]] = max( c[j]+lp[i], c[j+lw[i]] )
  print max(c)
  print c.index(max(c))

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

Submission status: Accepted

Solution code:
case=0
while True:
    try:
        case+=1
        W=input()
        if W==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(W+1)] for j in range(N)]
        table[0][0],table[0][data[0][1]]=0,data[0][0]
        for i in range(1,N):
            for j in range(W+1):
                table[i][j]=table[i-1][j]
            for j in range(W+1):
                if table[i-1][j]!=-1 and j+data[i][1]<=W and\
                   table[i-1][j]+data[i][0]>table[i][j+data[i][1]]:
                    table[i][j+data[i][1]]=table[i-1][j]+data[i][0]
        print "Case "+str(case)+':'
        m=max(table[N-1])
        print m
        print table[N-1].index(m)
    except:
        break

Submission status: Accepted

Solution code:
def sol():
    dp=[0]*(w+1)
    for i in l:
        for j in range(w-i[1],0,-1):
            if(dp[j]!=0):
                    dp[j+i[1]]=max(dp[j+i[1]],dp[j]+i[0])
        dp[i[1]]=max(dp[i[1]],i[0])
    print "Case %d:"%cnt
    print max(dp)
    print dp.index(max(dp))
cnt=0
while 1:
    w=int(raw_input())
    cnt+=1
    if w==0:
        break
    n=int(raw_input())
    l=[]
    for i in range(n):
        l.append(map(int,raw_input().split(',')))
    sol()

Submission status: Accepted

Solution code:
case = 1
while True:
    w_limit = int(input())
    if not w_limit:
        break
    n = int(input())
    treasures = [tuple(map(int, input().split(','))) for _ in range(n)]

    furoshiki = [0] * (w_limit + 1)
    for v, w in treasures:
        for j in range(w_limit, w - 1, -1):
            furoshiki[j] = max(furoshiki[j], furoshiki[j - w] + v)

    max_v = max_v_w = 0
    for w in range(w_limit + 1):
        if furoshiki[w] > max_v:
            max_v = furoshiki[w]
            max_v_w = w

    print('Case {}:'.format(case))
    print(max_v)
    print(max_v_w)
    case += 1

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    W = int(input())
    v = [0]
    w = [0]
    d = []
    m = []
    counter = 1
    result = []
    while W != 0:
        N = int(input())
        v[:] = [0]
        w[:] = [0]
        d[:] = []
        m[:] = []

        """the initialization of array d"""
        for x in range(W + 1):
            temp = [0] * (N + 1)
            d.append(temp)

        for x in range(W + 1):
            temp = [0] * (N + 1)
            m.append(temp)

        """prepare the dataset"""

        for x in range(N):
            i = input().split(',')
            v.append(int(i[0]))
            w.append(int(i[1]))

        """processing"""

        for weight in range(W + 1):
            for kind in range(N + 1):
                if weight != 0 and kind != 0:
                    if w[kind] > weight:
                        d[weight][kind] = d[weight][kind - 1]
                        m[weight][kind] = m[weight][kind - 1]
                    else:
                        if d[weight - w[kind]][kind - 1] + v[kind] > d[weight][kind - 1]:
                            d[weight][kind] = d[weight - w[kind]][kind - 1] + v[kind]
                            m[weight][kind] = m[weight - w[kind]][kind - 1] + w[kind]
                        elif d[weight - w[kind]][kind - 1] + v[kind] == d[weight][kind - 1]:
                            d[weight][kind] = d[weight][kind - 1]
                            if m[weight - w[kind]][kind - 1] + w[kind] < m[weight][kind - 1]:
                                m[weight][kind] = m[weight - w[kind]][kind- 1] + w[kind]
                            else:
                                m[weight][kind] = m[weight][kind - 1]
                        else:
                            d[weight][kind] = d[weight][kind - 1]
                            m[weight][kind] = m[weight][kind - 1]

        result.append("Case " + counter.__str__() + ":")
        result.append(d[W][N])
        result.append(m[W][N])

        W = int(input())
        counter += 1

    for line in result:
        print(line)

Submission status: Accepted

Solution code:
cnt=0
while 1:
    cnt+=1
    w=int(raw_input())
    if w==0:break
    n=int(raw_input())
    tre=[map(int,raw_input().split(",")) for _ in xrange(n)]
    dp=[[0]*(w+1) for _ in xrange(n+1)]
    dp[0][0]=0
    for i in xrange(n):
        for j in xrange(w+1):
            if tre[i][1]>j:dp[i+1][j]=dp[i][j]
            else:
                dp[i+1][j]=max(dp[i][j],dp[i][j-tre[i][1]]+tre[i][0])
    print('Case '+str(cnt)+":")
    print(dp[n][w])
    print(dp[n].index(dp[n][w]))

Submission status: Accepted

Solution code:
for i in range(1, 100):
    W = int(input())
    if not W:
        break
    N = int(input())
    data = [tuple(map(int, input().split(','))) for _ in range(N)]
    dp = [[[0, 0] for j in range(W + 1)] for i in range(N + 1)]
    print('Case {0}:'.format(i))
    for i in range(1, N + 1):
        for j in range(W + 1):
            if data[i - 1][1] <= j:
                pt = dp[i - 1][j - data[i - 1][1]][:]
                for k in range(2):
                    pt[k] += data[i - 1][k]
                dpt = dp[i - 1][j][:]
                if pt[0] > dpt[0]:
                    dp[i][j] = pt
                elif dpt[0] > pt[0]:
                    dp[i][j] = dpt
                else:
                    dp[i][j] = pt if pt[1] < dpt[1] else dpt
            else:
                dp[i][j] = dp[i - 1][j]
    for i in range(2):
        print(dp[N][W][i])

Submission status: Accepted

Solution code:
class Knapack(object):
    def __init__(self, data, limit):
        self.limit = limit
        data_size = len(data)
        self.C = [[0]*(limit+1) for _ in range(data_size+1)]
        self.data = data[:]

    def solve(self):
        for i in range(1, len(self.data)+1):
            i_value = self.data[i-1][0]
            i_weight = self.data[i-1][1]
            for w in range(1, self.limit+1):
                if i_weight <= w:
                    if i_value + self.C[i-1][w-i_weight] > self.C[i-1][w]:
                        self.C[i][w] = i_value + self.C[i-1][w-i_weight]
                    else:
                        self.C[i][w] = self.C[i-1][w]
                else:
                    self.C[i][w] = self.C[i-1][w]


if __name__ == '__main__':
    # ??????????????\???
    # limit = 50
    # data = [[60, 10], [100, 20], [120, 30], [210, 45], [10, 4]]
    case_no = 1
    while True:
        limit = int(input())
        if limit == 0:
            break
        num_of_items = int(input())
        data = []
        for i in range(num_of_items):
            data.append(list(map(int, input().split(','))))

        # ????????????????????????????§£???
        ks = Knapack(data, limit)
        ks.solve()

        # ???????????¨???
        target = ks.C[len(data)][limit]
        weight = limit
        for w in range(limit, 0, -1):
            if ks.C[len(data)][w] == target:
                weight = w
        print('Case {0}:'.format(case_no))
        print('{0}\n{1}'.format(target, weight))
        case_no += 1

Submission status: Accepted

Solution code:
Case_num = 1
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    List = [[0] * (W + 1)] * (N + 1) #????????? w??\????????°n??\?????§??????????????????????????§
    for i in range(1,N + 1):
        v,w = map(int,input().split(","))
        for j in range(W,w - 1,-1):
            List[i][j] = max(List[i - 1][j] ,List[i - 1][j - w] + v)
    print("Case",Case_num,end = ":\n")
    print(List[N][W])
    print(List[N].index(List[N][W]))
    Case_num += 1

Submission status: Accepted

Solution code:
cnt=0
while True:
    cnt+=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],dp[j-w]+v)
    wgt=0
    for i in range(W+1):
        if max(dp)==dp[i]:
            wgt=i
            break
    print("Case {0}:".format(cnt))
    print(max(dp))
    print(wgt)

Submission status: Accepted

Solution code:
cnt=0
while True:
    cnt+=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],dp[j-w]+v)
    wgt=0
    md=max(dp)
    for i in range(W+1):
        if md==dp[i]:
            wgt=i
            break
    print("Case {0}:".format(cnt))
    print(md)
    print(wgt)

Submission status: Accepted

Solution code:
cnt = 0
while True:
    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: Accepted

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+1):
        if dp[W]==dp[i]:break
    print('Case %d:\n%d\n%d'%(c,dp[W],i))
    c+=1

Submission status: Accepted

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]+v:dp[j]=dp[j-w]+v
    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: Accepted

Solution code:
ctr = 1
while True:
    w = int(input())
    if w==0: break
    dp = [0]*(w+1)

    n = int(input())
    for i in range(n):
        vi, wi = map(int, input().split(","))
        for j in range(w,wi-1,-1):
            dp[j] = max(dp[j],dp[j-wi]+vi)

    print("Case "+str(ctr)+":")
    print(max(dp))
    print(dp.index(max(dp)))
    ctr += 1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042

??\?£?
"""

class Knapack(object):
    def __init__(self, data, limit):
        self.limit = limit
        data_size = len(data)
        self.C = [[0]*(limit+1) for _ in range(data_size+1)]
        self.data = data[:]

    def solve(self):
        for i in range(1, len(self.data)+1):
            i_value = self.data[i-1][0]
            i_weight = self.data[i-1][1]
            for w in range(1, self.limit+1):
                if i_weight <= w:
                    if i_value + self.C[i-1][w-i_weight] > self.C[i-1][w]:
                        self.C[i][w] = i_value + self.C[i-1][w-i_weight]
                    else:
                        self.C[i][w] = self.C[i-1][w]
                else:
                    self.C[i][w] = self.C[i-1][w]


if __name__ == '__main__':
    # ??????????????\???
    # limit = 50
    # data = [[60, 10], [100, 20], [120, 30], [210, 45], [10, 4]]
    case_no = 1
    while True:
        limit = int(input())
        if limit == 0:
            break
        num_of_items = int(input())
        data = []
        for i in range(num_of_items):
            data.append(list(map(int, input().split(','))))

        # ????????????????????????????§£???
        ks = Knapack(data, limit)
        ks.solve()

        # ???????????¨???
        target = ks.C[len(data)][limit]
        weight = limit
        for w in range(limit, 0, -1):
            if ks.C[len(data)][w] == target:
                weight = w
        print('Case {0}:'.format(case_no))
        print('{0}\n{1}'.format(target, weight))
        case_no += 1

Submission status: Accepted

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

import sys
import os
import math
import itertools

case = 1
for s in sys.stdin:

    # capacity
    C = int(s)
    if C == 0:
        break

    N = int(input())

    V = [0]
    W = [0]

    # max value table of (N+1) x (C+1)
    VT = [[0 for i in range(C+1)] for j in range(N+1)]
    WT = [[0 for i in range(C+1)] for j in range(N+1)]

    for i in range(N):
        v, w = map(int, input().split(','))
        V.append(v)
        W.append(w)

    for i in range(1, N+1):
        for j in range(1, C+1):
            if j >= W[i]:
                # can load
                value_on_load = VT[i-1][j - W[i]] + V[i]
                value_not_load = VT[i-1][j]

                weight_on_load = WT[i-1][j - W[i]] + W[i]
                weight_not_load = WT[i-1][j]

                if value_on_load > value_not_load:
                    VT[i][j] = value_on_load
                    WT[i][j] = weight_on_load
                elif value_on_load == value_not_load:
                    VT[i][j] = value_on_load
                    WT[i][j] = min(weight_on_load, weight_not_load)
                else:
                    VT[i][j] = value_not_load
                    WT[i][j] = weight_not_load
            else:
                VT[i][j] = VT[i - 1][j]
                WT[i][j] = WT[i - 1][j]

    print('Case {}:'.format(case))
    case += 1
    print(VT[N][C])
    print(WT[N][C])

Submission status: Accepted

Solution code:
case = 0
while True:
    W = int(input())
    if W == 0:
        break
    N, case = int(input()), case + 1
    items = [[0,0]] + [list(map(int, input().split(','))) for _ in range(N)]
    C = [[0 for _ in range(W+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        for w in range(1, W+1):
            if items[i][1] <= w:
                C[i][w] = max(items[i][0]+C[i-1][w-items[i][1]], C[i-1][w])
            else:
                C[i][w] = C[i-1][w]
    maxv = max(C[-1])
    print("Case {0}:\n{1}\n{2}".format(case, maxv, C[-1].index(maxv)))

Submission status: Accepted

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])+dp[i+1][capa-int(data[i][1])][1]
    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
 
    count += 1

Submission status: Accepted

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)
    C_num += 1

Submission status: Accepted

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

  vl = [0]
  wl = [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])
        else:
          dp[i][j] = dp[i-1][j]
  ls = dp[N].copy()
  ls.reverse()
  max_w = W
  for i in range(1,W+1):
    if ls[i] == dp[N][W]:
      max_w -= 1
    else:
      break

  print("Case "+str(c)+":")
  print(dp[N][W])
  print(max_w)