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 <stdio.h>
#include <math.h>

using namespace std;


int w;
int num;
int caseN;

int *dataV,*dataW;
int maxV,maxW;

void calc(int n,int sumV,int sumW){
	if(sumW>w){
		return;
	}
	if(n==num){
		if(maxV<=sumV){
			maxV=sumV;
			maxW=sumW;
		}
		return;
	}
	else{
		calc(n+1,sumV,sumW);
		calc(n+1,sumV+dataV[n],sumW+dataW[n]);
	}

}

int main(){

	char tmp;
	caseN=0;

	while(cin>>w){
		if(w==0){
			 break;
		}
		cin>>num;
		dataV = new int(num);
		dataW = new int(num);
		maxV=0;
		maxW=0;
		
		for(int i=0;i<num;i++){
			cin>>dataV[i];
			cin>>tmp;
			cin>>dataW[i];
		}
		calc(0,0,0);

		cout<<"Case "<<caseN+1<<":"<<endl;
		cout<<maxV<<endl;
		cout<<maxW<<endl;

		caseN++;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)
  
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
  
#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

#define INF 1000000000

typedef long double Real;
typedef complex<Real> P;
Real dot(P a,P b){return real(conj(a)*b);}
Real cross(P a,P b){return imag(conj(a)*b);}

int main(){
  int cnt = 1;
  while(true){
    int w;
    cin>>w;
    if(w==0)break;
    int n;
    cin>>n;
    vi dp(w+1,-INF);
    dp[0] = 0;
    REP(_,n){
      int val,wei;
      scanf("%d,%d",&val,&wei);
      for(int i=w;i>=0;--i){
        if(i-wei<0)break;
        dp[i] = max(dp[i],dp[i-wei]+val);
      }
    }
    int mxval = 0, thenwei = 0;
    REPR(i,w+1){
      if(dp[i]>mxval){
        mxval = dp[i];
        thenwei = i;
      }
    }
    printf("Case %d:\n",cnt);
    cout<<mxval<<endl<<thenwei<<endl;
    ++cnt;
  }
  return 0;
}

C++: /*#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
	
	return 0;
}*/
/*
1
y eazqyp pnop pngtg ye obmpngt xmybp mr lygw
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
#define rep(i,n) for(int i=0; i<n; i++)
int dp[1001][1001];
 
int main(){
    int W, cnt=1;
    while( cin >> W, W ){
        int n, v[1000], w[1000];
        memset( dp, 0, sizeof(dp) );
        cin >> n;
        rep(i,n){
            scanf("%d,%d", &v[i], &w[i]);
        }
        dp[0][0] = 0;
    	
        
    	rep(i,n){
            rep(j,W+1){
                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 mw = 0;
        rep(i,W+1){
            if( dp[n][i]>dp[n][mw] ) mw = i;
        }
    	
    	/*for(int i = 0;i < n;i++){
    		for(int j = 0;j < W+1;j++){
    			cout << dp[i][j] << " ";
    		}
    		cout << endl;
    	}*/
    	
        cout << "Case " << cnt << ":" << endl;
        cnt++;
        cout << dp[n][mw] << endl;
        cout << mw << endl;
    }
	return 0;
}
/*
20
5
60,5
100,10
120,15
210,20
10,2
*/

C++: #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int,int> P;
typedef struct tre{
  int c,w;
};
P dp[1005][1005];
tre t[1005];
P solve(int i,int rem); 
int w,n;
int main(void){
  P ans;
  for(int l=1;;l++){
    scanf("%d",&w);
    if(!w)break;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d,%d",&t[i].c,&t[i].w);
    memset(dp,-1,sizeof(dp));
    ans=solve(0,w);
    printf("Case %d:\n%d\n%d\n",l,ans.first,w-ans.second);
  }
}

P solve(int i,int rem){
  P res;
  if(dp[i][rem].first>=0)return dp[i][rem];
  if(i>=n){
    res.first=0;
    res.second=rem;
    return res;
  }
  if(t[i].w>rem){
    res=solve(i+1,rem);
  }
  else{
    res=solve(i+1,rem);
    P temp=solve(i+1,rem-t[i].w);
    temp.first+=t[i].c;
    res=max(res,temp);
  }
  return dp[i][rem]=res;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};

queue<int>q;

bool calc(){
  int W;cin>>W;
  if(W==0)return true;
  int N;cin>>N;

  int v[1010],w[1010];
  for(int t=1;t<=N;t++){
    char c;
    cin>>v[t]>>c>>w[t];
  }
  static int dp[1010][1010];  //dp[n][w]:=n個目までから、総重量w以下で選んだ時の最大総和価値
  memset(dp,0,sizeof(dp));

  for(int i=0;i<N;i++){
    for(int j=0;j<=W;j++){

      if(w[i+1]>j){
        dp[i+1][j]=dp[i][j];
      }else{
        dp[i+1][j]=max(dp[i][j],dp[i][j-w[i+1]]+v[i+1]);
      }

    }
  }

  int ans_w;
  for(int w=0;w<=W;w++){
    if(dp[N][w]==dp[N][W]){
      ans_w=w;
      break;
    }
  }

  q.push(dp[N][W]);
  q.push(ans_w);
  return false;
}

signed main(){
  while(true){
    bool flag=calc();
    if(flag)break;
  }

  int t=1;
  while(!q.empty()){
    cout<<"Case "<<t<<":"<<"\n";
    cout<<q.front()<<"\n";q.pop();
    cout<<q.front()<<"\n";q.pop();
    t++;
  }
  return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <sstream>
using namespace std;
typedef pair<int,int> P;

const int W_MAX = 1000;
const int N_MAX = 1000;

int v[N_MAX + 1], w[N_MAX + 1];
int N,W;
P memo[N_MAX + 1][W_MAX +1];

P bfs(int i, int j)
{
	if(i == N)return P(0,0);
	if(memo[i][j] >= P(0,0)){
		return memo[i][j];
	}
	P p;
	if(w[i] > j){
		p = bfs(i+1,j);
	}
	else{
		P p1,p2;
		p1 = bfs(i + 1,j);
		p2 = bfs(i + 1,j - w[i]);
		p2.first += v[i];p2.second += w[i];
		if(p1.first == p2.first){
			if(p1.second < p2.second){
				p = p1;
			}
			else{
				p = p2;
			}
		}
		else{
			p = max(p1,p2);
		}
	}
	return memo[i][j] = p;
}

int main()
{
	int c = 1;
	while(cin >> W,W){
		cin >> N;
		fill((P*)memo,(P*)(memo+N_MAX+1),P(-1,-1));
		for(int i = 0; i < N; ++i){
			cin >> v[i]; cin.ignore(1,','); cin >> w[i];
		}
		cout << "Case " << c++ << ':' << endl;
		P p = bfs(0,W);
		cout << p.first << endl << p.second << endl;
	}
}