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: #!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools

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

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

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

Python: 

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)

Python: def f():
 c=0
 for W in iter(input,'0'):
  c+=1
  W=int(W)
  d=[0]*-~W
  for _ in[0]*int(input()):
   v,w=map(int,input().split(','))
   for i in range(W,w-1,-1):
    if d[i]<d[i-w]+v:d[i]=d[i-w]+v
  print(f'Case {c}:\n{d[W]}\n{d.index(d[W])}')
if'__main__'==__name__:f()

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

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

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())
    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(1, N+1):
        v, w = map(int, input().split(','))
        for j in range(1, w):
            V[k2][j] = V[k1][j]
            W[k2][j] = W[k1][j]
        for j in range(w, lim+1):
            d = j - w
            if V[k1][d] + v >= V[k1][j]:
                V[k2][j] = V[k1][d] + v
                W[k2][j] = W[k1][d] + w
            else:
                V[k2][j] = V[k1][j]
                W[k2][j] = W[k1][j]
        k1, k2 = k2, k1
    print(V[k1][lim], W[k1][lim], sep='\n')