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 <vector>
using namespace std;

struct treasure{
	int value;
	int weight;
};

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

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

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  int m;
  int co=0;
  while(cin>>m,m){
    co++;
    int n;
    cin>>n;
    vector<int>in(m,0);
    rep(i,n){
      int a,b;
      char d;
      cin>>a>>d>>b;
      for(int i=m;i>0;i--){
	if(i-b<0)continue;
	if(i!=b&&!in[i-b])continue;
	in[i]=max(in[i-b]+a,in[i]);
      }
      //rep(i,m+1)cout<<in[i]<<" "<<i<<endl;
      //cout<<" "<<endl;
    }
    int ans1=0,ans2=0;
    for(int i=m-1;i>0;i--){
      if(ans1<=in[i]){ans1=in[i];ans2=i;}
    }
    cout<<"Case "<<co<<":"<<endl;
    cout<<ans1<<endl<<ans2<<endl;
  }
}

C++: #include<iostream>
using namespace std;
int main(){
  int dp[1001][1001];
  int n,W;
  int v[1000],w[1000];
  int num=0;
  while(cin>> W,W){
    num++;
    cin>> n;
    for(int i=0;i<n+1;i++){
      dp[0][i]=0;
    }

    for(int i=0;i<n;i++){
      char c;
      cin>> v[i]>> c>> w[i];
    }

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

    int mv=0,mw;
    for(int j=0;j<=W;j++){
      if(mv<dp[n][j]){
	mv=dp[n][j];
	mw=j;
      }
    }
    for(int i=0;i<=n;i++){
      for(int j=0;j<=W;j++){
	cout<< dp[i][j];
      }
      cout<< endl<< endl;
    }

    cout<< "Case "<< num<< ":"<< endl;
    cout<< mv<< endl;
    cout<< mw<< endl;
  }
}

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

using namespace std;

int main( void )
{
	int map[1001], save[1001];
	int w; long long count;
	count = 1;
	while(cin >> w, w) {
		++w;
		for(int i=0; i < w; ++i) map[i] = save[i] = 0;
		int n, value, weight;
		cin >> n;
		scanf("%d,%d", &value, &weight);
		save[weight] = map[weight] = max(save[weight], value);
		for(int i=1; i < n; ++i) {
			scanf("%d,%d", &value, &weight);
			save[weight] = max(save[weight], value);
			for(int j=0; j < w; ++j) {
				if(map[j]) {
					int ww = j + weight;
					if(ww < w)
						save[ww] = max(save[ww], map[j] + value);
					else
						save[j] = max(save[j], map[j]);
				}
			}
			for(int j=0; j < w; ++j) {
				map[j] = save[j]; save[j] = 0;
			}
		}
		int Max = 0, idx;
		for(int i=1; i < w; ++i) {
			if(Max < map[i]) {
				Max = map[i];
				idx = i;
			}
		}
		cout << "Case " << count++ << ':' << endl;
		cout << Max << endl;
		cout << idx << endl;
	}

	return 0;
}

C++: //Solution for aoj:0042 A Thief
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
using namespace std;
int w, n, c;
char a;
int trs[1001][2];
int dp[1001][1001];
int main(){
	while (cin >> w){
		if (!w)
			return 0;
		c++;
		cin >> n;
		for (int i = 1; i <= n; i++){
			cin >> trs[i][0] >> a >> trs[i][1];
		}
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= w; j++){
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				if (j >= trs[i][1])
					dp[i][j] = max(dp[i][j], dp[i - 1][j - trs[i][1]] + trs[i][0]);
			}
		}
		for (int i = 1; i <= w; i++){
			if (dp[n][i] == dp[n][w]){
				cout << "Case " << c << ':' << endl << dp[n][i] << endl << i << endl;
				break;
			}
		}
	}
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<climits>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; i++)
#define FOR(i, j, k) for(int i = j; i < k; i++)
#define P pair<int, int>
const int INF = INT_MAX / 2;

int main(){
    int w;
    while(cin >>w && w){
        int n;
        cin >>n;
        vector< vector<int> > dp(n + 1, vector<int>(w + 1));
        REP(i, dp.size()){
            REP(j, dp[i].size()){
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 0;
        //input begin
        vector<P> j(n + 1);
        string str;
        getline(cin, str);
        FOR(i, 1, n + 1){
            getline(cin, str);
            stringstream ss(str);
            int a, b;
            char c;
            ss >>a >>c >>b;
            j[i].first = a;
            j[i].second = b;
        }
        //input end

        FOR(i, 1, dp.size()){
            int value = j[i].first, weight = j[i].second;
            REP(j, dp[i].size()){
                if(j >= weight && j - weight >= 0){
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value);
                } else{
                    dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                }
            }
        }

        int ans = -1;
        REP(i, dp[0].size()){
            if(dp[n][i] > ans){
                ans = dp[n][i];
            }
        }
        cout <<ans <<endl;
    }
    return 0;
}