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 <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 <= j)
					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][j - 1], dp[i + 1][j]));
				if(ans.first == dp[i + 1][nw] && ans.second > nw)
					ans = P(dp[i + 1][nw], nw);
				else if(ans.first < dp[i + 1][nw]) ans = P(dp[i + 1][nw], nw);
			}
		}

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

C++: #include<iostream>
#include<algorithm>
#include<string>
#include<typeinfo>
#include<cstdlib>
using namespace std;
int b[1000][1001];
int main() {
	int w, n;
	int sum = 1;
	while (cin >> w&&w != 0) {
		cin >> n;
		int a[1000][2];
		for (int i = 0; i < n; i++) {
			string h;
			cin >> h;
			h += ",";
			string k = "";
			int l = 0;
			for (int j = 0; j < h.length(); j++) {
				if (h[j] == ',') {
					a[i][l] = atoi(k.c_str());
					k = "";
					l++;
				}
				else
					k += h[j];
			}
		}
		int sum1 = 0, sum2 = 1002;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= w; j++) {
				b[i][j] = -1;
				if (j == 0) b[i][j] = 0;
			}
		}
		b[0][a[0][1]] = a[0][0];
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= w; j++) {
				int l = -1;
				if (j - a[i][1] >= 0) {
					if (b[i - 1][j - a[i][1]] != -1 && b[i - 1][j] != -1)
						l = max(b[i - 1][j], b[i - 1][j - a[i][1]] + a[i][0]);
					else if (b[i - 1][j - a[i][1]] != -1)
						l = b[i - 1][j - a[i][1]] + a[i][0];
					else if (b[i - 1][j] != -1)
						l = b[i - 1][j];
				}
				else if (b[i - 1][j] != -1)
					l = b[i - 1][j];
				b[i][j] = max(l, b[i][j]);
			}
		}
		for (int i = w; i >= 0; i--) {
			if (b[n - 1][i] >= sum1) {
				sum1 = b[n - 1][i];
				sum2 = i;
			}
		}
		cout << "Case " << sum << ":" << endl;
		cout << sum1 << "\n" << sum2 << endl;
		sum++;
	}
}

C++: #include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
using namespace std;

int fun(int a,int b){
	if(a>b)return a;
	return b;
}

int main(){
	int W,N,v[1001],w[1001],mat[1001][1001],max,mw;
	for(int c=1;;c++){
		cin >> W;
		if(W==0)break;
		cin >> N;
		for(int i=1;i<=N;i++){
			scanf("%d,%d",&v[i],&w[i]);
		}
max=0;
mw=0;
		for(int i=0;i<=N;i++){
			for(int j=0;j<=W;j++){
				if(i==0) mat[i][j] = 0;
				else{
					if(j<w[i]) mat[i][j] = mat[i-1][j];
					else mat[i][j] = fun(mat[i-1][j],mat[i-1][j-w[i]]+v[i]);
					if(i==N){
						if(max<mat[i][j]){
							max = mat[i][j];
							mw = j;
						}
					}
				}
			}
		}
		printf("Case %d:\n%d\n%d\n",c,max,mw);
	}
	
	return 0;
}

C++: #include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

int w,n;
vector< pair<int,int> > v;

int** GetArray(int w,int h){
	int** pt = new int*[w];
	for(int i=0;i<w;i++){
		pt[i] = new int[h];
		for(int j=0;j<h;j++){
			pt[i][j] = 0;
		}
	}
	return pt;
}

void DeleteArray(int** pt,int w){
	for(int i=0;i<w;i++){
		delete[] pt[i];
	}
	delete[] pt;
}

int main(){
	int setno = 1;
	int a,b;
	while(scanf("%d",&w) != EOF){
		if(w == 0){break;}
		scanf("%d",&n);
		printf("Case %d:\n",setno);
		v.clear();
		for(int i=0;i<n;i++){
			scanf("%d,%d",&a,&b);
			v.push_back(make_pair(a,b));
		}
		int** dp = GetArray(n + 1,w + 1);
		for(int j=0;j<=w;j++){
			//printf("j:%d\n",j);
			dp[0][j] = 0;
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<=w;j++){
				//printf("%d:%d\n",i,j);
				if(j < v[i].second){
					dp[i][j] = dp[i-1][j];
				}else{
					dp[i][j] = max(dp[i-1][j] , dp[i-1][j-v[i].second] + v[i].first);
				}
			}
		}
		int ans = dp[n][w];
		int answ = -1;
		for(int i=0;i<=w;i++){
			if(dp[n][i] == ans){
				answ = i;
				break;
			}
		}
		printf("%d\n%d\n",ans,answ);
		DeleteArray(dp,n + 1);
		setno++;
	}
}