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 <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
using namespace std;

class info
{
public:
	int value;
	vector <bool> visited;

	info()
	{
		value = 0;
		visited = vector <bool>( 1001, false );
	}
};

int main( void )
{
	int case_no = 1;
	int w_max;
	while ( cin >> w_max && w_max )
	{
		cout << "Case " << case_no << ":" << endl;

		// Â
		int n;
		cin >> n;

		// îñ
		vector <int> v( n );
		vector <int> w( n );

		// üÍ
		for ( int i = 0; i < n; i++ )
		{
			string in;
			cin >> in;
			replace( in.begin(), in.end(), ',', ' ' );

			int vi, wi;
			istringstream is( in );
			is >> vi >> wi;

			v[i] = vi;
			w[i] = wi;
		}

		// sort
		for ( int i = 0; i < n-1; i++ )
		{
			for ( int j = i+1; j < n; j++ )
			{
				if ( w[i] > w[j] )
				{
					swap( w[i], w[j] );
					swap( v[i], v[j] );
				}
				else if ( w[i] == w[j] )
				{
					if ( v[i] < v[j] )
					{
						swap( w[i], w[j] );
						swap( v[i], v[j] );
					}
				}
			}
		}

		vector <info> dp( w_max + 1 );

		for ( int i = 0; i < n; i++ )
		{
			int& wi = w[i];
			int& vi = v[i];

			if ( dp[wi].value < vi )
			{
				dp[wi].value = vi;
				dp[wi].visited[i] = true;
			}
		}

		for ( int i = 0; i <= w_max; i++ )
		{
			if ( dp[i].value <= 0 )
				continue;

			for ( int j = 0; j < n; j++ )
			{
				int& wj = w[j];
				int& vj = v[j];

				if ( dp[i].visited[j] )
					continue;

				if ( i + wj > w_max )
					continue;

				dp[i+wj].value		= dp[i].value + vj;
				dp[i+wj].visited	= dp[i].visited;
				dp[i+wj].visited[j]	= true;
			}
		}

		int maxw = 0;
		int maxv = 0;
		for ( int i = 0; i <= w_max; i++ )
		{
			if ( dp[i].value <= 0 )
				continue;

			if ( maxv < dp[i].value )
			{
				maxw = i;
				maxv = dp[i].value;
			}
		}

		cout << maxv << endl;
		cout << maxw << endl;

		case_no ++;
	}

	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#define N1 1001
using namespace std;
int Change(string);
void DP();
int N,W,n,v[N1],w[N1],dp[N1][N1];
int main(){
  int t,len,i,j;
  string in;
  n=1;
  while(1){
    cin >> W;
    if(W==0) break;
    cin >> N;
    for(i=1;i<=N;i++){
      cin >> in;
      len=in.size();
      for(j=0;j<len;j++){
	if(in[j]==','){
	  t=j;
	  break;
	}
      }
      v[i]=Change(in.substr(0,t));
      w[i]=Change(in.substr(t+1,len-t-1));
    }
    DP();
  }
  return 0;
}
int Change(string s){
  int ret=0,len=s.size(),i=0,x=1;
  while(len){
    ret=ret*x+(s[i]-'0');
    x=10;
    i++;
    len--;
  }
  return ret;
}
void DP(){
  int i,j,sum[N1][N1],wsum;
  for(i=0;i<=W;i++) dp[0][i]=0,sum[0][i]=0;
  for(i=0;i<=N;i++) dp[i][0]=0,sum[i][0]=0;
  for(i=1;i<=N;i++){
    for(j=1;j<=W;j++){
      if(j>=w[i]){
	if(dp[i-1][j]<=dp[i-1][j-w[i]]+v[i]){
	  dp[i][j]=dp[i-1][j-w[i]]+v[i];
	  sum[i][j]=1;
	}else{
	  dp[i][j]=dp[i-1][j];
	  sum[i][j]=0;
	}
      }else{
	dp[i][j]=dp[i-1][j];
	sum[i][j]=0;
      }
    }
  }
  wsum=0;
  int cp=W;
  for(i=N;i>=1;i--){
    if(sum[i][cp]==1){
      wsum+=w[i];
      cp-=w[i];
    }
  }
  cout << "Case " << n << ':' << endl;
  n++;
  cout << dp[N][W] << endl << wsum  << endl;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int w,c=0;
  while(cin >>w,w){
    c++;
    int n,t[1500][2]={0},dp[150][150]={0};
    cin >>n;
    for(int i=0; i<n; i++) scanf("%d,%d",&t[i][0],&t[i][1]);
    for(int i=0; i<n; i++){
      for(int j=0; j<=w; j++){
	if(j+t[i][1]<=w) dp[i+1][j+t[i][1]] = max(dp[i][j+t[i][1]],dp[i][j]+t[i][0]);
	dp[i+1][j] = max(dp[i][j],dp[i+1][j]);
      }
    }
    int m=0,ans;
    for(int i=0; i<=w; i++){
      if(m<dp[n][i]){m = dp[n][i];ans = i;}
    }
    cout <<"Case "<<c<<endl<<m<<endl<<ans<<endl;
  }
  return 0;
}

C++: #include <iostream>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
	int weight;
	int n,v,w,c=0;
	int dp[1001][1001];
	while(scanf("%d\n",&weight) && weight){
		c++;
		rep(i,1001)rep(j,1001)dp[i][j]=0;
		
		scanf("%d\n",&n);
		for(int k=1;k<=n;k++){
			scanf("%d,%d\n",&v,&w);
			for(int i=0;i<=w;i++){
				dp[k][i] = dp[k-1][i];
			}
			for(int i=w;i<=weight;i++){
				dp[k][i] = max(dp[k-1][i],dp[k-1][i-w]+v);
			}
		}
		/*for(int k=0;k<=n;k++){
			for(int i=0;i<=weight;i++)
				printf("%4d",dp[k][i]);
			puts("");
		}*/
		printf("Case %d:\n",c);
		printf("%d\n",dp[n][weight]);
		for(int i=0;i<=weight;i++){
			if(dp[n][i]==dp[n][weight]){
				printf("%d\n",i);
				break;
			}
		}
	}
}

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;
int v[1000], w[1000];

int main(void){
    int cs = 1;
    while(cin >> W && W){
        int dp[1000+1][1000+1] = {};
        cin >> n;
        REP(i, n){
            int a, b;
            scanf("%d, %d", &a, &b);
            v[i] = a;
            w[i] = b;
        }

        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]);
                }
            }
        }

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

C++: #define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;


int main(){
	int W;
	int idx=1;
	while(~scanf("%d",&W)){
		if(W==0) break;
		int N;
		vector<P> bag;

		cin >> N;

		int** dp = new int*[N+1];
		for(int i=0;i<N+1;i++){
			dp[i] = new int[1000]();
		}



		for(int i=0;i<N;i++){
			int v,w;
			scanf("%d,%d",&v,&w);
			bag.push_back(P(v,w));
		}

		for(int i=0;i<bag.size();i++){
			for(int j=0;j<=W;j++){
				if(j < bag[i].second){
					dp[i+1][j] = dp[i][j];
				}
				else{
					dp[i+1][j] = max(dp[i][j], dp[i][j-bag[i].second] + bag[i].first);
				}
			}
		}


		int max_v=-1;
		int max_w=-1;
		for(int j=0;j<=W;j++){
			if(max_v < dp[N][j]){

				max_v = dp[N][j];
				max_w = j;
			}
		}

		printf("Case %d:\n%d\n%d\n",idx++,max_v,max_w);
	}


}