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<algorithm>
using namespace std;
int main(){
  int w,n,a,b,ca=0;
  
  while(scanf("%d",&w) && w != 0){
    scanf("%d",&n);
    int dp[n+1][w+1];
    fill_n(*dp,(n+1)*(w+1),0);

    for(int i = 1;i <= n;i++){
      scanf("%d,%d",&a,&b);
	for(int j = 0;j <= w;j++){
	  if(j < b) dp[i][j] = dp[i-1][j];
	  else dp[i][j] = max(dp[i-1][j],dp[i-1][j-b]+a);
	}
      }
    
    ca++;
    printf("Case %d:\n",ca);
    printf("%d\n",dp[n][w]);
    for(int i = w-1;i >= 0;i--){
      if(dp[n][w] != dp[n][i]){
	printf("%d\n",i+1);
	break;
      }
    }
  }    
  
  return (0);
}

C++: #define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>

using namespace std;

typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;

int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

static const double EPS = 1e-8;

int v[1000];
int w[1000];
int dp[1001][1001];

int main(){
	int W,N;
	int idx = 1;
	while(~scanf("%d",&W)){
		if(W==0) break;
		memset(dp,0,sizeof(dp));

		scanf("%d",&N);
		
		for(int i=0;i<N;i++){			
			scanf("%d,%d",&v[i],&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-w[i]] + v[i],dp[i+1][j]);
				}
			}
		}

		int resv = 0;
		int resw = 0;
		for(int i=1;i<=N;i++){
			for(int j=0;j<W;j++){
				if(dp[i][j] > resv){
					resv = dp[i][j];
					resw = j;
				}
			}
		}

		printf("Case %d:\n%d\n%d\n",idx++,resv,resw);
	}
}

C++: #include <cstdio>
#include <algorithm>
#define MAX_N 1000
#define MAX_W 1000
using namespace std;
int W;
int N; 

int w[MAX_N]; 
int v[MAX_N]; 
int dp[MAX_N + 1][MAX_W + 1];
bool input() 
{
  scanf("%d", &W);
  if(!W) return false;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) 
  {
    scanf("%d,%d", &v[i], &w[i]);
  }
  return true;
}
void solve() 
{

  for (int i = 0; i < N; i++) 
  {
    for (int j = 0; j <= W; j++) 
    {
      if (j < w[i])
      {
        dp[i + 1][j] = dp[i][j];
      } 
      else 
      {
        dp[i + 1][j] = (short)max((int)dp[i][j], dp[i][j - w[i]] + v[i]);
      }
    }
  }
}

int main() 
{

  int cnt = 0;

  while (input())
  {
    solve();
    int i;
    for (i = W; i >= 0; i--) 
    {
      if (dp[N][W] != dp[N][i]) break;
    }
    printf("Case %d:\n", ++cnt);
    printf("%d\n", dp[N][W]);
    printf("%d\n", i + 1);
  }

  return 0;
}

C++: #include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <memory.h>
#include <cassert>

using namespace std;


#define all(c) ((c).begin()), ((c).end())
#define debug(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)

#define mp make_pair
#define fst first
#define snd second
#define pb push_back


const double EPS = 1e-10;


typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef complex<double> P;


int main() {
	int nCase = 1;
	for (int W; cin >> W, W != 0; ) {
		int n; cin >> n;
		int p[1000], w[1000];
		rep(i, n) {
			char c; cin >> p[i] >> c >> w[i];
		}
		int dp[10001];
		memset(dp, 0, sizeof(dp));
		int answ = W + 1, ansp = 0;
		rep(i, n) for(int j = W; j >= w[i]; j--) {
			dp[j] = max(dp[j], dp[j - w[i]] + p[i]);
			if (ansp == dp[j]) answ = min(answ, j);
			else if(ansp < dp[j]) {
				ansp = dp[j];
				answ = j;
			}
		}
		cout << "Case " << nCase << ":" << endl;
		cout << ansp << endl << answ << endl;
		nCase++;
	}
	
	return 0;
}

C++: #include <iostream>
#include <stdlib.h>

using namespace std;

void rec(int i, const int weight, const int n, int v[], int w[], int *sum_w, int *sum_v)
{
  //?????????
  if (i+1 == n) {
    if (weight >= w[i] + *sum_w) {
      *sum_w += w[i];
      *sum_v += v[i];
    } 
    
  }
  //?????§?????????
  else {
    int tmpw, tmpv;
    tmpw = *sum_w;
    tmpv = *sum_v;
    
    int w1, v1, w2, v2;
    //?¢??????\??????
    if (weight >= w[i] + tmpw) {
      *sum_w += w[i];
      *sum_v += v[i];
      
      rec(i+1, weight, n, v, w, sum_w, sum_v);
      
      w1 =  *sum_w;
      v1 =  *sum_v;

    } else { v1 = 0; }
    
    *sum_w = tmpw;
    *sum_v = tmpv;
    
    //?¢??????\?????????
    rec(i+1, weight, n, v, w, sum_w, sum_v);
    
    if (weight >= *sum_w) {
      w2 = *sum_w;
      v2 = *sum_v;
    }

    if (v1 > v2) {
      *sum_w = w1;
      *sum_v = v1;
    } else {
      *sum_w = w2;
      *sum_v = v2;
    }
    
  }
  
}

void rec2(int i, const int weight, const int n, int v[], int w[], int *sum_w, int *sum_v)
{
 
  if (i == n) {
    *sum_v = 0;
  }
  else {
    int tmpw, tmpv;
    tmpw = *sum_w;
    tmpv = *sum_v;
    
    int w1, v1, w2, v2;

    if (weight >= w[i] + tmpw) {
      *sum_w += w[i];
      
      rec2(1+i, weight, n, v, w, sum_w, sum_v);

      w1 = *sum_w;
      v1 = *sum_v + v[i];
    } else { v1 = -1; w1 = -1; }
    *sum_w = tmpw;
    *sum_v = tmpv;

    rec2(1+i, weight, n, v, w, sum_w, sum_v);

    w2 = *sum_w;
    v2 = *sum_v;

    if (v1 > v2) {
      *sum_w = w1;
      *sum_v = v1;
    } else {
      *sum_w = w2;
      *sum_v = v2;
    }
   
  }

}

int main(void)
{
  int count = 1;
  while (true) {
    
    int weight, n;
    cin >> weight;
    if (weight == 0) break;
    cin >> n;
    int v[n], w[n];
    char c;
    for (int i = 0; i < n; i++) cin >> v[i] >> c >> w[i];
    //??\?????????

    
    
    int huroshiki, value;
    int *sum_w, *sum_v;

    huroshiki = 0;
    value = 0;
    sum_w = &huroshiki; sum_v = &value;

    
    
    rec2(0, weight, n, v, w, sum_w, sum_v);
    
    cout << "Case " << count << ":" << endl;
    cout << value << endl;
    cout << huroshiki << endl;
    
    count++;
  }

  return 0;
}