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++
	}
}

C++: 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int main()
{
    int W;
	for(int caseNum = 1; cin >> W && W; caseNum++)
	{
		int N;
		cin >> N;
		
		vint prv(W + 1, 0);
		
		
		rep(i, N)
		{
			vint nxt(W + 1, 0);
			int val, wei;
			char k;
			
			cin >> val >> k >> wei;
			
			rep(j, W - wei + 1)
			{
				if(j == 0 || prv[j] != 0)
				{
					chmax(nxt[j + wei], prv[j] + val);
				}
			}
			
			prv = nxt;
		}
		
		
		int val = 0, wei;
		rep(i, W + 1)
		{
			if(val < prv[i])
			{
				wei = i;
				val = prv[i];
			}
		}
		
		
		cout << "Case " << caseNum << ":\n" << val << endl << wei << endl;
	}
}

C++: #include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>

using namespace std;

int main(void){
  int w, n;
  int cnt = 0;
  while(cin>>w,w){
    vector<pair<int,int> > v;
    long long dp[1001][1001];
    memset(dp, 0, sizeof(dp));
  
    cin>>n;

    for(int i = 0 ; i < n ; i++){
      int s,t;
      scanf("%d,%d",&s,&t);
      v.push_back(make_pair(s,t));
    }
    for(int i = n-1 ; i >= 0 ; i --){
      for(int j = 0 ; j <= w ; j ++){
	if(j < v[i].second) dp[i][j] = dp[i+1][j];
	else dp[i][j] = max(dp[i+1][j] , dp[i+1][j -v[i].second]+v[i].first);
      }						
    }

    cout<<"Case "<<++cnt<<":"<<endl;
    cout<<dp[0][w]<<endl;
    for(int i = w ; ; i--){
      if(dp[0][i] != dp[0][w]){
	cout<<i+1<<endl;
	break;
      }
    }
  }
}

C++: #include <cstdio>
#include <cstring>
#define MAX(a,b)((a)>=(b)?(a):(b))
int dp[1001],v[1000],w[1000];
int main() {
	int W,N,Case=1;
	while(scanf("%d",&W),W) {
		scanf("%d",&N);
		for(int i=0;i<N;i++) {
			scanf("%d,%d",&v[i],&w[i]);
		}
		memset(dp,0,sizeof(dp));
		for(int i=0;i<N;i++) {
			for(int j=W;j>=w[i];j--) {
				dp[j]=MAX(dp[j],dp[j-w[i]]+v[i]);
			}
		}
		int ans_w=W;
		for(int i=W-1;i>=0;i--) {
			if(dp[W]!=dp[i]) {ans_w=i+1; break;} 
		}
		printf("Case %d:\n",Case++);
		printf("%d\n%d\n",dp[W],ans_w);
	}
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int main()
{
    int W;
	for(int caseNum = 1; cin >> W && W; caseNum++)
	{
		int N;
		cin >> N;
		
		vint prv(W + 1, 0);
		
		
		rep(i, N)
		{
			vint nxt(prv);
			int val, wei;
			char k;
			
			cin >> val >> k >> wei;
			
			rep(j, W - wei + 1)
			{
				if(j == 0 || prv[j] != 0)
				{
					chmax(nxt[j + wei], prv[j] + val);
				}
			}
			
			prv = nxt;
		}
		
		
		int val = 0, wei;
		rep(i, W + 1)
		{
			if(val < prv[i])
			{
				wei = i;
				val = prv[i];
			}
		}
		
		
		cout << "Case " << caseNum << ":\n" << val << endl << wei << endl;
	}
}

C++: #include <cstdio>
#include <algorithm>

using namespace std;

int dp[1000][1001],t[1000],w[1000];

int main(){
  for(int c=1;;c++){
    int n,q,i,j;
    scanf("%d",&q); if(q==0) break;
    scanf("%d",&n);

    for(i=0; i<n; i++)
      scanf("%d,%d",&t[i],&w[i]);

    for(i=0; i<=q; i++)
      dp[0][i] = (i>=w[0])?t[0]:0;

    for(i=1; i<n; i++)
      for(j=0; j<=q; j++){
	/*if(j+w[i]<=q)
	  dp[i][j+w[i]] = dp[i-1][j]+t[i];
	  dp[i][j] = max(dp[i][j],dp[i-1][j]);*/
	if(j>=w[i])
	  dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+t[i]);
	else
	  dp[i][j] = dp[i-1][j];
      }

    int mw=0,mt=0;
    for(j=0; j<=q; j++)
      if(dp[n-1][j]>mt){
	mt = dp[n-1][j];
	mw = j;
      }

    /*    for(i=0; i<=q; i++)
      printf("%3d ",i);
      putchar('\n');
    for(i=0; i<n; i++){
      for(j=0; j<=q; j++)
	printf("%3d ",dp[i][j]);
      putchar('\n');
      }*/


    printf("Case %d:\n%d\n%d\n",c,mt,mw);
  }
}

C++: #include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>
#include<cmath>
using namespace std;
int inf = 1000000000;
// dp[i][j] = i ???????????§??§?????? j ??§?????????
// dp[i][j] = dp[i][j-?] + v[i];

int dp[1001][1001];

int main(){

  int W, N, l;
  l = 1;
  while(cin >> W){
    if( W == 0 ) break;
    cin >> N;
    vector<int> v(N);
    vector<int> w(N);
    for(int i=0; i<N; i++) scanf("%d,%d", &v[i], &w[i]);

    for(int i=0; i<1001; i++) for(int j=0; j<1001; j++) dp[i][j] = 0;

    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] ] + v[i]);
        dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
      }
    }

    int ansi = 0;
    int ans = 0;
    for(int i=1; i<=W; i++){
      if( ans <= dp[N][i] ){
        ans = dp[N][i];
        ansi = i;
      }
    }

    cout << "Case " << l << ":" << endl;
    cout << ansi << endl;
    cout << ans << endl;

    l++;
  }




  return 0;
}