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>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(5)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef complex<double> Point;
typedef long long ll;
const int INF = 114514810;
const int MOD = 100000007;
const double EPS = 1e-10;
const double PI = acos(-1.0);
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

int W, N, w[1005], v[1005];
P dp[1005][10005];

P solve(int i, int j)
{
	if (dp[i][j].first >= 0) return dp[i][j];
	if (i == N) return P(0, 0);
	P res;
	if (j < w[i]) res = solve(i + 1, j);
	else
	{
		P a = solve(i + 1, j);
		P b = solve(i + 1, j - w[i]);
		b.first += v[i]; b.second += w[i];
		if (a.first != b.first) res = max(a, b);
		else res = min(a, b);
	}

	return dp[i][j] = res;
}

int main()
{
	int cse = 0;
	while (cin >> W >> N, W)
	{
		cse++;
		MS(dp, -1);
		char c;
		REP(i, N) cin >> v[i] >> c >> w[i];
		cout << "Case " << cse << ":" << endl << solve(0, W).first << endl << solve(0, W).second << endl;

	}
}

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

int dp[1000];
int main(){
	int w, n, ans_w = 0, ans_val = 0;
	for (int dataset = 1; cin >> w, w; dataset++){
		int t_w, t_val;
		cin >> n;
		for (int i = 0; i < w; i++) dp[i] = -1;
		dp[0] = 0;
		for (int i = 0; i < n; i++){
			scanf("%d,%d", &t_val, &t_w);
			if (i == n - 1) for (int i = 0; i < 5000000000; i++){}
			for (int j = w - 1; j >= 0; j--){
				//printf("%d ", dp[j]);
				if (dp[j] == -1 || j + t_w >= w || dp[j + t_w] > dp[j] + t_val)
					continue;
				dp[j + t_w] = dp[j] + t_val;
			}
			//puts("");
		}
		for (int i = 0; i < w; i++){
			//printf("%d ", dp[i]);
			if (ans_val < dp[i]){
				ans_val = dp[i];
				ans_w = i;
			}
		}
		//puts("");
		printf("Case %d:\n%d\n%d\n", dataset, ans_val, ans_w);
	}
	return 0;
}

C++: #include<iostream>


using namespace std;

int value[1000][1000];

int main () {

	int count = 1;
	while ( true ) {

		int w, n;

		cin >> w;
		if ( w == 0 )
			break;
		cin >> n;

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

				value[i][j] = 0;

			}
		}


		int maxv, minw;

		maxv =0;
		minw = 100000;

		for ( int i=0; i<n; i++ ) {
			int v, ow;
			char ch;

			cin >> v >> ch >> ow;

			value[0][ow] = v;

			if ( maxv <= v ) {
				if ( maxv < v ) {
					maxv = v;
				}
				if (minw > ow ) {
					minw = ow;
				}
			}

		}
	

		for ( int i=0; i<n-1; i++ ) {
			for ( int j=0; j<1000; j++ ) {
				if ( value[i][j] != 0 ) {

					//value[i+1][j] = value[i][j];

					for ( int k=j+1; k<1000; k++ ) {
						if ( value[i][k] != 0 ) {
							if ( j+k < w && 2*(i+1)-1< n) {
								if ( value[2*(i+1)][k+j] < value[i][j] + value[i][k] ) {
									value[2*(i+1)][k+j] = value[i][j] + value[i][k];

									if ( maxv <= value[2*(i+1)][k+j] ) {
										if ( maxv < value[2*(i+1)][k+j] ) {
											maxv = value[2*(i+1)][k+j];
											minw = j+k;
										}
										else if (minw > j+k ) {
											minw = j+k;
										}
									}
								}
							}
						}
					}
				}
			}
		}
/*
		cout << endl;
		for ( int i=0 ;i<1000; i++ ) {
			for ( int j=0; j<n; j++ ) {
				cout << value[j][i] << "\t";
			}
			cout << endl;
		}
		cout << endl << endl;
*/

		cout << "Case " << count << ":" << endl;
		cout << maxv << endl << minw << endl << endl;

	}
}

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

struct treasure{
	int value;
	int weight;
};

bool comp(treasure t1, treasure t2){
	if(t1.weight <= t2.weight) return true;
	else return false;
}

int main(){
	int w;
	const int maxw = 10000;
	int count = 1;
	while(cin >> w){
		if(w == 0) break;
		int n;
		int cost[maxw + 1];
		int best[maxw + 1];
		for(int i = 0; i <= maxw; i++){
			cost[i] = 0;
			best[i] = 0;
		}
		vector<treasure> treasures;
		cin >> n;
		for(int i = 0; i < n; i++){
			treasure t;
			char c;
			cin >> t.value >> c >> t.weight;
			treasures.push_back(t);
		}
		sort(treasures.begin(), treasures.end(), comp);
		for(int j = 0; j < n; j++){
			for(int k = 1; k <= w; k++)
				if(k >= treasures[j].weight)
					if(cost[k] < cost[k - treasures[j].weight] + treasures[j].value)
					{
						cost[k] = cost[k - treasures[j].weight] + treasures[j].value;
						best[k] = j;
					}
		}
		cout << "Case" << " " << count++ << ":" << endl;
	}
	return 0;
}

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

using namespace std;

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,j,k) for(int i=j;i<(k);i++)
#define foreach(T,c,i) for(T::iterator i=c.begin();i!=c.end();i++)
typedef vector<int> Array;
typedef vector<Array> Mat;
const int INF = 99999999;
int N,W,a,b,ans_num=0;
const int MAX_N = 1000;
const int MAX_W = 1000;
int dp[MAX_N+1][MAX_W+1];
Array v,w;

void solve()
{
	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 << dp[N][W] << endl;
	int MIN = INF;
	rep(i,N+1)rep(j,W+1){
		if(dp[i][j]==dp[N][W]) MIN = min(MIN,j);
	}
	cout << MIN << endl;
	
}
		
int main(){
	while(1){
		cin >> W >> N;
		if(W==0) return 0;
		ans_num++;
		memset(dp,0,sizeof(dp));
		v.clear();
		w.clear();
		rep(i,N){
			scanf("%d,%d",&a,&b);
			v.pb(a);
			w.pb(b);
		}
		cout << "Case " << ans_num << ":" << endl;
		solve();
	}	
	return 0;	
}