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 = [[None for _ in range(W + 1)] for _ in range(N)]
    def loop(i, w):
        if i == N:
            return (0, 0)
        if cache[i][w] is not None:
            return cache[i][w]
        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]))

Python: 

def rec(i, j):
	if 3000 < i or 3000 < j:
		while True:
			print("aaa")

	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

case = 1
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(2500)] for i in range(2500)]
	(v, w) = rec(0, W)

	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

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

case = 1
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(2500)] for i in range(2500)]
	(v, w) = rec(0, W)

	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

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

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

C++: #include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int dp[1000][1000] = {{0}};
int main(){
  int w,n;
  char ch;
  int P[1000]={0},W[1000]={0},t = 1;
  while(cin >> w,w ){
    cin >> n;
    for(int i = 0 ; i < n ; i++ ){
      cin >> P[i] >> ch >> W[i];
    }
    for(int i = 0 ; i < n ; i++ ){
      for(int j = 0 ; j <= w ; j++ ){
	if(j - W[i] >= 0 ){ 
	  dp[i+1][j] = max(dp[i][j],dp[i][j-W[i]] + P[i]);
	}else dp[i+1][j] = dp[i][j];
      }
    }
    cout << "Case " << t << ":" << endl;
    for(int i = w ; i >= 0 ; i--){
      if(dp[n][i] != dp[n][w]){
	cout << dp[n][w] << endl << i + 1 << endl;
	break;
      }
    }
    t++;
  }
  return 0;
}