Go: package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

const MaxW = 1000
const MaxN = 1000

type Tuple struct {
	Value  int
	Weight int
}

func nextLine(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func solve(w int, n int, vws []Tuple) Tuple {
	var dp [MaxN + 1][MaxW + 1]int

	for i := 0; i < n; i++ {
		for j:= w; j > 0; j-- {
			if j < vws[i].Weight {
				dp[i + 1][j] = dp[i][j]
			} else {
				dp[i + 1][j] = int(math.Max(float64(dp[i][j]), float64(dp[i][j - vws[i].Weight] + vws[i].Value)))
			}
		}
	}

	maxValue := dp[n][w]
	minWeight := w

	for j := w - 1; j > 0; j-- {
		if maxValue == dp[n][j] {
			minWeight = j
		} else {
			break
		}
	}

	return Tuple{Value: maxValue, Weight: minWeight}
}

func main() {
	var sc = bufio.NewScanner(os.Stdin)
	index := 1
	for {
		var w, n int
		w, _ = strconv.Atoi(nextLine(sc))
		if w == 0 {
			return
		}
		n, _ = strconv.Atoi(nextLine(sc))

		vws := make([]Tuple, n, n)
		for i := 0; i < n; i++ {
			array := strings.Split(nextLine(sc), ",")
			v, _ := strconv.Atoi(array[0])
			w, _ := strconv.Atoi(array[1])
			vws[i] = Tuple{Value: v, Weight: w}
		}

		t := solve(w, n, vws)
		fmt.Printf("Case %d:\n", index)
		fmt.Println(t.Value)
		fmt.Println(t.Weight)
		index++
	}
}

Python: # 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

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

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

Python: # 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

Python: # -*- 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)

Python: # 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');

Python: # -*- 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