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>

#define FOR(i, n, m) for(int i = (n);i < (m);i++)
#define REP(i, n) for(int i = 0;i < (n);i++)
#define PII pair<int, int>

typedef long long int lli;

using namespace std;

int n, W;
vector<int> v, w;
int dp[1000][1000+1];

int main(void){
    int cs = 1;
    while(cin >> W && W){
        cin >> n;
        REP(m, n){
            int a, b;
            scanf("%d, %d", &a, &b);
            v.push_back(a);
            w.push_back(b);
        }

        FOR(i, 1, n){
            FOR(j, 0, W+1){
                if(j - w[i] < 0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
                }
            }
        }

        cout << "Case " << cs << ":" << endl;
        cout << dp[n-1][W-1] << endl;
        int min_w = 100000000;
        REP(i, n){
            REP(j, W){
                if(dp[i][j] == dp[n-1][W-1]){
                    min_w = min(min_w, j);
                }
            }
        }
        cout << min_w << endl;
        cs++;
    }
    return 0;
}

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

int main(){
	int w, n, cnt = 1;
	char dum;
	vector< vector< int > > dp;
	vector< int > weight, value;
	
	while(cin >> w, w){
		cin >> n;
		
		weight.resize(n);
		value.resize(n);
		
		for(int i = 0; i < n; ++i){
			scanf("%d,%d", &(value[i]), &(weight[i]));
		}
		
		dp.resize(n + 1);
		for(int i = 0; i <= n; ++i){
			dp[i].resize(w + 1);
		}
		
		for(int i = 0; i <= w; ++i) dp[0][i] = 0;
		
		for(int i = 1; i <= n; ++i){
			for(int j = 0; j <= w; ++j){
				if(weight[i-1] > j){
					dp[i][j] = dp[i-1][j];
				}else{
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1]);
				}
			}
		}
		
		cout << "Case " << cnt << ":" << endl;
		cout << dp[n][w] << endl;
		for(int i = 0; i <= w; ++i){
			if(dp[n][i] == dp[n][w]){
				cout << i << endl;
				break;
			}
		}
		
		++cnt;
	}
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  for(int c=1,w; cin>>w,w; c++){
    int n,tr[1001][2] = {0};
    cin >>n;
    for(int i=1; i<=n; i++){
      scanf("%d,%d",&tr[i][0],&tr[i][1]);
    }
    int dp[1001][1001] = {0};
    for(int i=1; i<=n; i++){
      for(int j=0; j<=w; j++){
	if(j>=tr[i][1]){dp[j][i] = max(dp[j][i-1],dp[j-tr[i][1]][i-1]+tr[i][0]);}
	else{dp[j][i] = dp[j][i-1];}
      }
    }
    int pr = dp[w][n], val;
    for(int j=0; j<=w; j++){
      if(pr == dp[j][n]){val = j;break;}
    }
    cout <<"Case "<<c<<":"<<endl;
    cout <<pr<<endl<<val<<endl;
  }
  return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define MAX 1001

int dp[MAX][MAX],t,w,m;
int Val[MAX],Wei[MAX];

void judge(){
    
    for(int i = 1 ; i <= m ; i++){
        for(int j = 1 ; j <= w ; j++){
            int k = j - Wei[i];
            if(k < 0){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i-1][k]+Val[i]);
            }
        }
    }
    int ans_W=0,ans_C;
    for(int i = 1 ; i <= w ; i++){
        ans_W = max(ans_W,dp[m][i]);
    }
    for(int i = w ; i >= 1 ; i--){
        if(ans_W==dp[m][i]) ans_C = i;
    }
    
    cout << ans_W << endl;
    cout << ans_C << endl;
}

void print(){
    cout << "Case " << t++ << ":" << endl;
}

int main(){
    char c;
    
    t = 1;
    while(cin >> w,w){
        cin >> m;
        
        fill(dp[0],dp[MAX-1],0);
        Wei[0] = Val[0] = 0;
        
        print();
        for(int j = 1 ; j <= m ; j++) cin >> Val[j] >> c >> Wei[j];
        
        judge();
    }
    
    return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int W,N,w[1001],v[1001],ansW=0,ansV=0;
int memo[1001][1001],cou,ans2;
int func(int i,int j,int _v){
    //printf(" %d,%d,%d\n",i,j,_v);
    if(j>W)return 0;
    if(memo[i][j]>_v){
        return 0;
    }
    memo[i][j] = _v;
    if(i==N){
        if(ansV<_v){
            ansV = _v;
            ansW = j;
        }
        else if(ansV==_v && ansW>j){
            ansV = _v;
            ansW = j;
        }
        return _v;
    }
    //ans2=max(ans2,j);
    return max(func(i+1,j,_v),func(i+1,j+w[i],_v+v[i]));
    //ans2=max(ans2,j);
}
int main(){
    int tc=1;
    while(cin>>W,W){
        fill(memo[0],memo[0]+1001*1001,0);
        int ans=0,cou=0;
        cin>>N;
        for(int i=0;i<N;i++){
            scanf("%d,%d",&v[i],&w[i]);
        }
        func(0,0,0);
        cout<<"Case "<<tc<<":"<<endl<<ansV<<endl<<ansW<<endl;;
        tc++;
    }
}

C++: #include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <stack>
#define rep(i,k,n) for(int i=k;i<n;i++)
#define pb push_back

typedef long long ll;
using namespace std;
void komma(int& nedan,int& omosa){
  char inputl[100];
  cin>>inputl;
  rep(i,0,100){
    if(inputl[i]==',') {
      inputl[i]=0;
      nedan=atoi(inputl);
      omosa=atoi(inputl+i+1);
      break;
    }
  }
  //  cout <<nedan<<endl<<omosa<<endl;
}
int main(){

  int W,N,nedan,omosa,maxne,maxomo,count,tmp;
 
  vector<vector<int> >hukuro(1010);
  rep(i,0,1010)
    hukuro[i]=vector<int>(1010,0);
  count=0;
  cin>>W>>N;
  //cout<<"??\n";
  while(W){
    maxne=maxomo=0;
    rep(i,0,1000)
      hukuro[0][i]=0;
    komma(nedan,omosa);
    //cout<<"otto?\n";  
    hukuro[0][omosa]=nedan;
    rep(i,1,N){
    komma(nedan,omosa);
    rep(j,0,W+1){
      if(j>=omosa)
	hukuro[i][j]=max(hukuro[i-1][j],hukuro[i-1][j-omosa]+nedan);
      else hukuro[i][j]=hukuro[i-1][j];
      // cout<<i<<" "<<j<<endl<<hukuro[i][j]<<endl;
    }
    }
    for(int i=W;i>=0;i--)
      if(maxne<=hukuro[N-1][i]){
	maxne=hukuro[N-1][i];
	maxomo=i;
      }
    cout<<"Case "<<++count<<":\n"<<maxne<<endl<<maxomo<<endl;
    cin>>W>>N;
    //    cout<<"???\n";
    }

  return 0;
}

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

int w, z[1100][2] = {}, map[1100][1100] = {}, n, min_w = 20000000, max_v = 0;

int main(){
	int k = 1;
	while(cin >> w >> n){
		if (w == 0) break;
		min_w = 20000000;
		max_v = -1;
		for(int i = 1;i<=n;i++){
			char cmp;
			cin >> z[i][0] >> cmp >> z[i][1];
		}
		for(int i = 1;i<=n;i++){
			for(int j = 1;j<=w;j++){
				if (z[i][1] > j) continue;
				map[i][j] = max(map[i - 1][j], map[i - 1][j - z[i][1]] + z[i][0]);
				if(max_v < map[i][j]){
					max_v = map[i][j];
					min_w = j;
				}
				else if(max_v == map[i][j]){
					if (min_w > j) min_w = j;
				}
			}
		}
		cout << "Case " << k << ":" << endl
			<< max_v << endl
			<< min_w << endl;
		k++;
	}
	return 0;
}