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.h> 
using namespace std;

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

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]);
    /* 
   int tmp1,tmp2;
    tmp1 = rec(i+1,j);
    tmp2 = rec(i+1,j-w[i]) + v[i];
    if(tmp1 < tmp2){
      res = tmp2;
    }else{
      res = tmp1;
    }
    */
  }
  return dp[i][j] = res;
}


int main(){

  int num = 1;

  while(1){
    cin >> W;
    if(W == 0) break;
    cin >> N;
    //テ・ツ按敕ヲツ慊淌・ツ個?
    /*
    for(int i = 0; i < 1001; i++){
      w[i] = v[i] = -1;
      for(int j = 0; j < 1001; j++)
	dp[i][j] = -1; 
    }
    */
    memset(dp,-1,sizeof(dp));
    memset(w,-1,sizeof(w));
    memset(v,-1,sizeof(v));


    //テ・ツ?・テ・ツ環?
    char tmp;
    for(int i = 0; i < N; i++) cin >> v[i] >> tmp >> w[i];

    int ans = rec(0,W);

    // dpテゥツ?催・ツ按療」ツつ津・ツ?ィテ」ツ?ヲテ・ツ淞凝」ツつ?」ツつ?
    for(int i = 0; i < N; i++){
      for(int j = 0; j <= W; j++){
	if(dp[i][j] == -1)
	  rec(i,j);
      }
    }   
  
    cout << "Case "<< num  << ":"<< endl;
    num++;
    cout << ans << endl; 
    int j;
    for( j = 0; dp[0][j] != ans ; j++){}
    cout << j << endl;
    
  }
  return 0;
}

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

using namespace std;

const int NUM_MAX = 1001;
int dp[NUM_MAX][NUM_MAX];
int we[NUM_MAX], v[NUM_MAX];
int w, n;

void solve()
{
    int max_idx;

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

    max_idx = 0;
    for (int j = 0; j <= w; j++)
        if (dp[n][j] == dp[n][w])
            max_idx = j;
        
    cout << dp[n][w] << '\n' << max_idx << endl;
}

int main()
{
    int cas = 1;

    while (cin >> w, w) {
        char ch;

        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> v[i] >> ch >> we[i];

        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= w; j++)
                dp[i][j] = 0;

        cout << "Case " << cas++ << ":\n";
        solve();
    }

    return 0;
}

C++: #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int dp[1010][1010][2];

int main() {
	int w,n,num=0;;
	while(w=in(),n=in(),w){
		memset(dp,0,sizeof(dp));
		int a,b,i;
		for(i=0;i<n;i++){
			scanf("%d,%d",&a,&b);
			int k;
			for(k=b;k<=w;k++){
				if(dp[i][k][0]<dp[i][k-b][0]+a
				||dp[i][k][0]==dp[i][k-b][0]+a&&dp[i][k][1]>dp[i][k-b][1]+b){
					dp[i+1][k][0]=dp[i][k-b][0]+a;
					dp[i+1][k][1]=dp[i][k-b][1]+b;
				}else{
					dp[i+1][k][0]=dp[i][k][0];
					dp[i+1][k][1]=dp[i][k][1];
				}
			}
			//cout<<dp[w]<<endl;
		}
		cout<<"Case "<<++num<<":"<<endl;
		cout<<dp[n][w][0]<<endl;
		cout<<dp[n][w][1]<<endl;
	}
	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <string>
#include <cmath>
#include <map> 
#include <sstream>
#include <cstdio>
#include <complex>
#include <cstring>
using namespace std;
 
const int MAX= 10000100;

#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define rep(i,a) loop(i,0,a)
#define all(a) (a).begin(),(a).end()
#define ll long long int
#define gcd(a,b) __gcd(a,b)
#define pb(a) push_back(a)
int GCD(int a, int b) {if(!b) return a; return gcd(b, a%b);}
int lcm(int a, int b) {return a*b / gcd(a, b);}

const int MAX_W = 1000;
const int MAX_N = 1000;
int W,N;
int v[MAX_N];
int w[MAX_N];
int dp[MAX_W + 1];
void solve(){
  fill(dp, dp+W + 1 , 0);
  rep(i,N){
    for(int j = W ; j >= 0 ; j --){
      if(j - w[i] >= 0){
	dp[j] = max(dp[j] , dp[j-w[i]] + v[i]);
      }
    }
  }
  printf("%d\n",dp[W]);
  for(int i = W ; i >= 0 ; i --){
    if(dp[W] != dp[i]){
      printf("%d\n",i+1);
      break;
    }
  }
}

int main(void){
  int i = 0 ;
  while(scanf("%d",&W),W){
    printf("Case %d:\n",++i);
    scanf("%d",&N);
    rep(i,N){
      scanf("%d,%d",&v[i],&w[i]);
    }
    solve();
  }
  return 0;
}

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

#define INF 10000000

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

// dp[i][j] : i番目以降のものから重さｊ以下になるように選んだ時の最大値
int dp[1002][1002];

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 < 1001; i++){
      w[i] = INF;
      v[i] = -1;
    }
 
    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++){
	rec(i,j);
      }
    }
    
    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;

}