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 <cstdio>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <cfloat>

#include <map>

#include <utility>

#include <set>

#include <iostream>

#include <memory>

#include <string>

#include <vector>

#include <algorithm>

#include <functional>

#include <sstream>

#include <complex>

#include <stack>

#include <queue>

#include <numeric>

#include <cstring>



#define rep(i, n) for(int i = 0; i < (n); i++)

#define pb push_back



using namespace std;



typedef long long ll;

typedef pair<int, int> P;

typedef vector<int> vi;

typedef vector<vi> vvi;



const int INF = 1 << 29;

const double EPS = 1e-9;

const int MAX_N = 1000;

const int MAX_W = 10000;



int dp[MAX_N + 1][MAX_W + 1];



int main(){

	int n, cap;

	int v[MAX_N], w[MAX_N];

//	int dp[MAX_N + 1][MAX_W + 1];



	while(1){

		memset(dp, 0 , sizeof(dp));

		scanf("%d", &cap);

		if(cap == 0) break;

		scanf("%d", &n);



		rep(i, n){

			scanf("%d,%d", &v[i], &w[i]);

		}



		for(int i = 0; i < n; i++){

			for(int j = 0; j <= cap; j++){

				if(w[i] > cap){

					dp[i+1][j] = dp[i][j];

				}

				if(w[i] < cap){

					dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);

				}

			}

		}

		cout << dp[n][cap] << endl;

	}

}

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

#define INF 1000000000

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

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

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 < 1000; 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;

}

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

#define N 1000
#define W 1000
#define INF 10001

#define max(a,b) (a>b?a:b)

int main() {
	static int dp[N+1][W+1];
	int tw[N+1], tv[N+1];
	int w, n, mv, mw, c=0; char dummy;
	for(int i=0; i<N+1; ++i) {
		for(int j=0; j<N+1; ++j) {
			dp[i][j] = 0;
		}
	}
	while(1) {
		cin >> w;
		if(!w) break;
		c++; mw = INF; mv = 0;
		cin >> n;
		for(int i=1; i<=n; ++i) cin >> tv[i] >> dummy >> tw[i];
		for(int i=1; i<=n; ++i) {
			for(int j=0; j<=w; ++j) {
				if(j-tw[i]>=0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-tw[i]]+tv[i]);
			}
		}
		for(int i=0; i<=w; ++i) {
			if(mv<dp[n][i]) {
				mw = i; mv = dp[n][i];
			}
		}
		cout << "Case " << c << ":" << endl;
		cout << mv << "\n" << mw << endl;
	}
	return 0;
}

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

#define INF 1e6

using namespace std;

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

int main(void){
	int tem=1;
	int vmax,wmax;
	while(true){
		vmax=0;
		memset(dp,-1,sizeof(dp));
		cin >> W >> N;
		if(!W)
			break;
		dp[0]=0;
		for(int i=0;i<N;i++){
			scanf("%d,%d",&v,&w);
			for(int j=W-w;j>=0;j--){
				if(dp[j]>=0)
					dp[j+w]=max(dp[j+w],(dp[j]+v));
			}
		}
		for(int i=0; i<=W; i++){
			cout << i << ' ' << dp[i] << endl;
			if(dp[i]>vmax){
			vmax=dp[i];
			wmax=i;
			}
		}
		cout << "Case "<<tem<<':'<<endl;
		cout <<  vmax << endl << wmax <<endl;
		tem++;
	}
	return 0;
}

C++: #include<iostream>
#include<stdio.h>
using namespace std;
int dp[1005][1005];
int main(){
  int W,N,v[1000],w[1000];
  int n=1;
  int lastj=0;
  char jyama;
  while(cin>>W&&W){
    cin>>N;
    for(int i=0;i<N;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    for(int i=0;i<=N;i++){
      for(int j=0;j<=W;j++){
	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]);
	  if(j>0&&dp[i][j]!=dp[i][j-1]) lastj=j;
	}
      }
    }    
    cout<<"Case "<<n<<":"<<endl;
    cout<<dp[N][W]<<endl;
    cout<<lastj<<endl;
    ++n;
  }
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <set>

using namespace std;

#define ALL(co) co.begin(), co.end()
#define tpl(...) make_tuple(__VA_ARGS__)

typedef long long LL;
typedef pair<int, int> P; typedef pair<int, P> IP; typedef pair<P, P> PP;
typedef vector<int> Array; typedef vector<vector<int> > Array2;
typedef vector<LL> LArray; typedef vector<P> PArray; typedef vector<string> SArray;

const int INF = 1 << 29;
const LL LINF = 1LL << 60;

inline int getInt() { int itiv; return (cin >> itiv, itiv); }
template <typename T> void readAll(vector<T>& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i]; }
template <typename T, typename U> void readAll(vector<pair<T, U> >& vec) { char c;for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i].first >> c >> vec[i].second; }
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };
inline bool between(int min, int max, int n) { return min <= n && n <= max; }
inline bool inRange(int begin, int end, int n) { return begin <= n && n < end; }
inline bool inRange(int size, int n) { return 0 <= n && n < size; }

int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
int dr[] = { 0, -1, 0, 1 }, dc[] = { -1, 0, 1, 0 };

int w, n;

// index, weight
int dp[1010][1010];
PArray treasure;

int main(void)
{
	ios::sync_with_stdio(false);
	int count = 1;
	while(cin >> w && w)
	{
		n = getInt();
		for (int i = 0; i <= n; i++)
		{
			memset(dp[i], 0, sizeof(dp[i]));
		}
		treasure.resize(n);
		readAll(treasure);
		P ans = P(-1, INF);
		for (int i = 0; i < n; i++)
		{
			int price = treasure[i].first, weight = treasure[i].second;
			for (int j = 0; j <= w; j++)
			{
				int nw = j + weight;
				if(nw <= w)
					dp[i + 1][nw] = max(dp[i][nw], max(dp[i + 1][nw - 1], max(dp[i + 1][nw], dp[i][j] + price)));
				if(j != 0) dp[i + 1][j] = max(dp[i + 1][j], max(dp[i + 1][j - 1], dp[i][j]));
				if(ans.first == dp[i + 1][j] && ans.second > j)
					ans = P(dp[i + 1][j], j);
				else if(ans.first < dp[i + 1][j]) ans = P(dp[i + 1][j], j);
			}
		}

		cout << "Case " << count << ':' << endl;
		cout << ans.first << endl << ans.second << endl;
		count++;
	}
	return 0;
}