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 <bits/stdc++.h>
using namespace std;

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int W,N;
int dp [1001] [1001];

int main()
{
	int testCase = 1;
	while(scanf("%d",&W),W){
		scanf("%d",&N);
		vector<int> x(N),y(N);
		FOR(i,0,N){
			scanf("%d,%d",&x [i],&y [i]);
		}
		memset(dp,0,sizeof(dp));
		FOR(i,0,N) FOR(j,0,W + 1){
			chmax(dp [i + 1] [j],dp [i] [j]);
			if(j + y [i] <= W) chmax(dp [i + 1] [j + y [i]],dp [i] [j] + x [i]);
		}
		pair<int,int> ans(-1,-1);
		FOR(j,0,W + 1){
			if(dp [N] [j] > ans.first){
				ans.first = dp [N] [j];
				ans.second = j;
			}
		}
		printf("Case %d:\n",testCase);
		printf("%d\n",ans.first);
		printf("%d\n",ans.second);
		testCase++;
	}

	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
/* 変数名を被らせない
   デバッグコードを取り除く */
#define ANSWER(x) cout<<x<<endl
#define debug(x) cout<<#x<<": "<<x
const int MAX_INT = 1000000;
int n,w,ans,cnt=1;
int value[1001],weight[1001];
int solve(int a,int b);
int main(){
  while(1){
    cin >> w;
    if(w==0)break;
    cin >> n;
    for(int i=0;i<n;i++){
      scanf("%d,%d",&value[i],&weight[i]);
    }
    ans = solve(0,w);
    for(int i=0;i<=w;i++){
      if(solve(0,i) == ans){
	cout <<"Case " << cnt <<':' << endl <<  ans <<endl << i << endl;
	break;
      }
    }
    cnt++;
  }
}
int solve(int a,int b){
  if(a == n)return 0;
    
  else if(b < weight[a])return solve(a+1,b);
  else return max(solve(a+1,b-weight[a])+value[a],solve(a+1,b));
}

C++: // 2014/09/13 Tazoe

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;

int main()
{
	for(int I=1; ; I++){
		int W;
		cin >> W;

		if(W==0)
			break;

		int DP[1001] = {0};

		int N;
		cin >> N;

		for(int i=0; i<N; i++){
			string s;
			cin >> s;

			for(int j=0; j<s.size(); j++){
				if(s[j]==','){
					s[j] = ' ';
					break;
				}
			}

			istringstream is(s);
			int v, w;
			is >> v >> w;

			for(int j=W; j-w>=0; j--){
				DP[j] = max(DP[j], DP[j-w]+v);
			}
		}

		int V_max = DP[W];
		int W_max = W;
		for(int i=W-1; i>=0; i--){
			if(DP[i]>=V_max){
				V_max = DP[i];
				W_max = i;
			}
		}

		cout << "Case " << I << ":" << endl;
		cout << V_max << endl;
		cout << W_max << endl;
	}

	return 0;
}

C++: //57
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  int c=0;
  for(int W;cin>>W,W;){
    c++;
    int N;
    cin>>N;
    int val[1001];
    fill_n(val,1001,-1);
    val[0]=0;
    while(N--){
      int v,w;
      (cin>>v).ignore()>>w;
      for(int i=1000;i-w>=0;i--){
	if(val[i-w]>=0){
	  val[i]=max(val[i],val[i-w]+v);
	}
      }
    }
    int i;
    for(i=W;val[i]==val[i-1];i--) ;
    cout<<"Case "<<c<<':'<<endl;
    cout<<val[i]<<endl;
    cout<<i<<endl;
  }
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 10007;
static const int INF = 1 << 25;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { -1, 0, 1, 0,  1, -1,  1, -1 };
static const int dy[] = { 0, -1, 0, 1 , 1,  1, -1, -1 };

int can_take, n, cnt = 0;
PII dp[ 1001 ][ 1001 ];
vector<PII> Item;
PII ans;

PII solve( int w, int now ) {
	if ( dp[ now ][ w ].first >= 0 ) {
		return dp[ now ][ w ];
	}
	if ( now == n || w == can_take ) {
		return PII( 0, w );
	}
	PII res = PII( 0, 0 );
	if ( w + Item[ now ].second <= can_take ) {
		res = solve( w + Item[ now ].second, now + 1 );
		res.first += Item[ now ].first;		
	}

	PII d = solve( w, now + 1 );
	if ( res.first < d.first || ( res.first == d.first && res.second > d.second ) ) {
		res = d;
	}
	return dp[ now ][ w ] = res;
}

int main() {
	while ( ~scanf( "%d", &can_take ) && can_take ) {
		printf( "Case %d:\n", ++cnt );
		scanf( "%d", &n );
		Item.resize( n );
		for ( int i = 0; i < n; i++ ) {
			scanf( "%d,%d", &Item[ i ].first, &Item[ i ].second );
		}
		for ( int i = 0; i < 1001; i++ ) {
			for ( int j = 0; j < n; j++ ) {
				dp[ i ][ j ] = PII( -1, -1 );
			}
		}
		ans = solve( 0, 0 );
		printf( "%d\n", ans.first );
		printf( "%d\n", ans.second );
	}
	return 0;
}

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

int main(){
    int w,n,va,we;
    int dp[1000];
    char c;
    vector<pair<int,int> >vec;
    
    while(cin>>w>>n,w){
        for(int i=0;i<n;i++){
            cin>>va>>c>>we;
            vec.push_back(make_pair(va, we));
        }
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            int tv=vec[i].first, tw=vec[i].second;
            for(int j=w;j>=0;j--){
                if(tw==j)continue;
                if(tw+j<=w){
                    dp[tw+j]=max(dp[tw+j],dp[j]+tv);
                }
            }
        }
        int aw=0,av=0;
        for(int i=0;i<=w;i++) {
            if(dp[i]>av){
                aw=i;
                av=dp[i];
            }
        }
        cout<<av<<endl<<aw<<endl;
        vec.clear();
    }
}