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 <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){
		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-1] << endl;
	int MIN = INF;
	rep(i,N+1)rep(j,W){
		if(dp[i][j]==dp[N][W-1]) MIN = min(MIN,j);
	}
	cout << MIN << endl;
	
}

		
int main(){
	while(1){
		cin >> W ;
		if(W==0) return 0;
                cin >> N;
		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;	
}

C++: // 他人のを拝借
#include <iostream>#include <algorithm>#include <cassert>#include <cctype>#include <cstdio>#include <math.h>#include <map>#include <queue>#include <string>using namespace std; int W,N,v[1000],w[1000],dp[1001][1001];char c; int main(){    int cn=0;    while(cin>>W){        if(W==0)return 0;        cn++;        cin>>N;        for(int i=0;i<N;i++)cin>>v[i]>>c>>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]);            }        }        int V=dp[N][W],w2=W;        while(dp[N][w2]==V)w2--;        cout<<"Case "<<cn<<":"<<endl<<dp[N][W]<<endl<<w2+1<<endl;    }}

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

int dp[1001][10001];
int v[1001], w[1001];

int main(){
	int W;

	int k = 1;
	while (std::cin >> W, W){
		int n;

		std::cin >> n;
		char a;
		for (int i = 0; i < n; i++)std::cin >> v[i] >> a >> w[i];

		memset(dp, -1, sizeof(dp));

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

				if (dp[i][j] != -1){
					dp[i + 1][j] = std::max(dp[i + 1][j], dp[i][j]);
					if (j + w[i] <= W)dp[i + 1][j + w[i]] = std::max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
				}
			}
		}

		int max = 0, id = 0;
		for (int i = 1; i <= W; i++){
			if (max < dp[n][i])max = dp[n][i], id = i;
		}
		std::cout << "Case " << k << ":" << std::endl << max << std::endl << id << std::endl;

		k++;
	}

	return 0;
}

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

#define N_MAX 1000	// ??????????????° ?????§???
#define W_MAX 1000  // ?¢¨?????????????????????????????? ?????§???

using namespace std;

int dp[N_MAX+1][W_MAX+1];
int v[N_MAX+1], w[N_MAX+1];
int N, W;

pair<int, int> knapsack() {
	int ans_w, ans_v;

	// ?????????
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= W; j++) {
			dp[i][j] = 0;
		}
	}

	// ????????¨???
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= W; j++) {
			if (w[i] <= j) {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	// ???????§£?????¢???
	ans_v = -1;
	ans_w = 0;
	for (int i = W; i >= 1; i--) {
		if (ans_v <= dp[N][i]) {
			ans_v = dp[N][i];
			ans_w = i;
		}
	}

	return make_pair(ans_v, ans_w);
}

int main() {
	int cont = 1;
	char c;
	pair<int, int> ans;

	while (cin >> W) {
		if (W == 0)  break;

		cin >> N;

		for (int i = 1; i <= N; i++) {
			cin >> v[i] >> c >> w[i];
		}

		ans = knapsack();

		printf("Case %d:\n%d\n%d\n", cont, ans.first, ans.second);
		
		cont++;
	}

	return 0;
}

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

int dp[1001][1001];

int main()
{
	int c = 1;

	while(1)
	{
		for(int i = 0; i <= 1000; i++)
			for(int j = 0; j <= 1000; j++)
				dp[i][j] = 0;

		int w, n;
		cin>>w>>n;
		if(w == 0)break;
		int treasure[1000];
		int price[1000];

		for(int i = 0; i < n; i++)
			scanf("%d,%d", &price[i], &treasure[i]);

		for(int i = 0; i < n; i++){
			for(int j = 0; j <= w; j++){
				if(j < treasure[i])
					dp[i + 1][j] = dp[i][j];
				else
					dp[i + 1][j] = max(dp[i][j], dp[i][j - treasure[i]] + price[i]);
			}
		}
	
		int ansWeight;
		for(ansWeight = w - 1; w >= 0; ansWeight--)
			if(dp[n][w] > dp[n][ansWeight])break;
			
		cout << "Case " << c++ <<":"<<endl;
		cout << dp[n][w] << endl;
		cout << ansWeight + 1 << endl;
	}

	return 0;
}

C++: #include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <cstdio>
#include <cctype>
#include <queue>
#include <complex>
#include <climits>
#include <cstring>
#include <cstdlib>

typedef long long ll;

using namespace std;

int dp[1010][1010];

int main(void){
	int W, N;
	int w[10010], v[10010];
	int c = 0;

	while(cin >> W){
		c++;
		if(!W) break;
		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){
				dp[i][j] = 0;
			}
		}

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

		int weight;
		for(int j=W; j>=0; --j){
			if(dp[N][j] == dp[N][W]) weight = j;
			else break;
		}

		cout << "Case " << c << ":" << endl << dp[N][W] << endl << weight << endl;

	}


	return 0;
}