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 <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>

using namespace std;

vector< vector<int> > dp;
vector<int> w,v;
int n,weight;

int rec(int i,int j){

	if(dp[i][j]>=0) return dp[i][j];

	int res;
	if(i==n) res=0;
	else if(j<w[i]) res=rec(i+1,j);
	else res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);

	return dp[i][j]=res;
}

int main(){

	int count=1;
	cin>>weight;
	while(weight!=0){
		cin>>n;
		w.resize(n); v.resize(n);
		for(int i=0;i<n;i++) scanf("%d,%d",&v[i],&w[i]);

		dp = vector< vector<int> >(n+1);
		for(int i=0;i<n+1;i++) dp[i]=vector<int>(weight+1,-1);

		int ans_v=rec(0,weight);
		cout<<"Case "<<count<<":"<<endl<<ans_v<<endl;
	
		weight--;
		while(weight){
			dp = vector< vector<int> >(n+1);
			for(int i=0;i<n+1;i++) dp[i]=vector<int>(weight+1,-1);
			if(ans_v!=rec(0,weight)) break;
			weight--;
		}
		cout<<weight+1<<endl;

		count++;
		cin>>weight;

	}


	return 0;

}

C++: #include <iostream>
#include <map>
#include <stdio.h>
int main(){
  using std::cin;
  using std::cout;
  using std::endl;
  using std::map;
  int weight,n,w,v,s,c=1;
  map<int,int> m;
  while(cin>>weight){
    if(!weight)return 0;
    cin>>n;
    map<int,int>::iterator it;
    for(;n;n--){
      scanf("%d,%d",&v,&w);
      if(m.empty()){m[w]=v;continue;}
      it = m.begin();
      while(it!=m.end()){
	s=(*it).second+v;
	  if((*it).first+w<weight){
	    if(m[(*it).first+w]<s)m[(*it).first+w]=(*it).second+v;
	  }
	it++;
      }
      m[w]=v;
    }
    it=m.end();
    it--;
    cout<<"Case: "<<c++<<(*it).second<<endl<<(*it).first<<endl;
    m.clear();
  }
}

C++: #include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int W, n;
  int t = 1;
  while (cin >> W) {
    if (W == 0) return 0;
    cin >> n;
    vi v(n), w(n);
    string s;
    rep(i, n) {
      getline(cin, s, ',');
      v[i] = stoi(s);
      cin >> w[i];
    }

    vvi dp(n+1, vi(W+1, -inf));
    dp[0][0] = 0;
    rep2(i, 1, n + 1) {
      rep(j, W + 1) {
        chmax(dp[i][j], dp[i-1][j]);
        if (j - w[i-1] >= 0) {
          chmax(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]);
        }
      }
    }

    cout << "Case " << t << ":" << endl;
    int ma_v = *max_element(all(dp[n]));
    int mi_w = inf;
    rep(j, W+1) {
      if (dp[n][j] == ma_v) {
        mi_w = j;
        break;
      }
    }
    cout << ma_v << endl;
    cout << mi_w << endl;

    t++;
  }
}

C++: #include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int dp[1001][1001];
int v[1001], w[1001];
int main() {
	int W, N;
	int cnt = 1;
	while (scanf("%d", &W), W) {
		scanf("%d", &N);
		rep(i, N)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]) dp[i + 1][j] = dp[i][j];
				else dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
			}
		}
		int Max = 0, Min = 0;
		for (int i = 0; i <= W; i++) {
			if (Max < dp[N][i]) { Max = dp[N][i]; Min = i; }
		}
		printf("Case %d:\n%d\n%d\n", cnt, Max, Min);
		cnt++;
	}
	return 0;
}

C++: //Solution for aoj:0042 A Thief
#include<bits/stdc++.h>
using namespace std;
#define int  long long unsigned int
int w, n, c;
char a;
int trs[1001][2];
int dp[1001][1001];
signed main(){
	while (cin >> w){
		if (!w)
			return 0;
		c++;
		cin >> n;
		for (int i = 1; i <= n; i++){
			cin >> trs[i][0] >> a >> trs[i][1];
		}
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= w; j++){
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				if (j >= trs[i][1])
					dp[i][j] = max(dp[i][j], dp[i - 1][j - trs[i][1]] + trs[i][0]);
			}
		}
		for (int i = 1; i <= w; i++){
			if (dp[n][i] == dp[n][w]){
				cout << "Case " << c << ':' << endl << dp[n][i] << endl << i << endl;
				break;
			}
		}
	}
}

C++: #include <iostream>
#include <cstring>
using namespace std;

#define INF 1000000000

int W,N;
int v[1000],w[1000];

// dp[i][j] : iテァツ閉ェテァツ崢ョテ、ツサツ・テゥツ卍催」ツ?ョテ」ツつづ」ツ?ョテ」ツ?凝」ツつ嘉ゥツ?催」ツ?陛ッツスツ甘、ツサツ・テ、ツクツ凝」ツ?ォテ」ツ?ェテ」ツつ凝」ツつ暗」ツ??」ツ?ォテゥツ?クテ」ツつ禿」ツ??ヲツ卍づ」ツ?ョテヲツ慊?・ツ、ツァテ・ツ?、
int dp[1000][1000];

int rec(int i, int j){
  if(dp[i][j] >= 0){
    return dp[i][j];
  }
  int res;
  if(i == N){
    res = 0;
  }else if( j < w[i] ){
    res = rec(i + 1 , j);
  }else{
    res = max( rec(i + 1,j) , rec(i+1, j-w[i]) + v[i] );
  }
  return dp[i][j] = res;
}

int main(){
  int x = 1;
  while(1){
   
    cin >> W;
    if(W == 0) break;

    cin >> N;
    memset(dp,-1,sizeof(dp));
    for(int i = 0; i < N; i++){
      v[i] = -1;
      w[i] = INF;
    }
    for(int i = 0 ; i < N ; i++){
      char tmp;
      cin >> v[i] >> tmp >> w[i];
      //  cout << v[i] <<" "<< w[i] << endl; 
    }
    
    for(int i = 0; i < N ; i++){
      for(int j = 0; j <= W ; j++){
	dp[i][j] = rec(i,j);
	//	cout << dp[i][j] << " ";
      }
      //cout << endl;
    }
    
    cout <<"Case " << x << endl;
    cout <<  dp[0][W] << endl;
    int t;
    for( t = 0; dp[0][W] != dp[0][t] ;t++){}
    cout << t << endl; 

    x++;

  }


  return 0;

}