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>
#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, c = 1;
    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_v = -1, ans_w;
        REP(i, dp[0].size()){
            if(dp[n][i] > ans_v){
                ans_v = dp[n][i];
                ans_w = i;
            }
        }
        cout <<"Case " <<c <<":" <<endl <<ans_v <<endl <<ans_w <<endl;
        c++;
    }
    return 0;
}

C++: #include<stdio.h>
#include<string.h>
#include<math.h>
int a,s,d[1001],f[1001],g[1001][1001],h,i,j,z,x=1;
int main(void)
{
	while(1){
		scanf("%d",&a);
		if(a==0)	break;
		scanf("%d",&s);
		for(i=0;i<s;i++)
			scanf("%d,%d",&d[i],&f[i]);
		for(i=0;i<s;i++){
			for(j=0;j<a;j++)
				g[i][j]=-1;
		}
		g[0][0]=0;
		for(i=0;i<s;i++){
			for(j=0;j<=a;j++){
				if(g[i][j]!=-1){
					if(g[i][j]>g[i+1][j])
						g[i+1][j]=g[i][j];
					if(j+f[i]<=a){
						if(g[i][j]+d[i]>g[i+1][j+f[i]])
							g[i+1][j+f[i]]=g[i][j]+d[i];
					}
				}
			}
		}
		/*for(i=0;i<s;i++){
			for(j=0;j<=a;j++)
				printf("%d ",g[i][j]);
			printf("\n");
		}*/
		h=0;
		for(i=0;i<=a;i++){
			if(h<g[s][i]){
				h=g[s][i];
				z=i;
			}
		}
		printf("Case %d:\n",x);
		printf("%d\n%d\n",h,z);
		x++;
	}
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int,int> P;

int main(){
	int W,N,cou=0;
	int tr[1001],we[1001];
	while(cin >> W , W){
		cou++;
		cin >> N;
		for(int i=1;i<=N;i++){
			scanf("%d,%d",&tr[i],&we[i]);
		}

		P dp[1010][1001];
		for(int i=0;i<=N;i++){
			for(int j=0;j<=N;j++){
				dp[i][j] = P(0,0);
			}
		}
		dp[0][0] = P(0,0);
		for(int i=1;i<=N;i++){
			dp[i][0] = P(0,0);
			for(int j=0;j<i;j++){
				if(dp[i-1][j].second+we[i] <= W){
					P p;
					p = P(dp[i-1][j].first+tr[i],dp[i-1][j].second+we[i]);
					if(p.first == dp[i-1][j+1].first){
						if(p.second < dp[i-1][j+1].second) dp[i][j+1] = p;
						else dp[i][j+1] = dp[i-1][j+1];
					}
					else if(p.first > dp[i-1][j+1].first){
						dp[i][j+1] = p;
					}
					else dp[i][j+1] = dp[i-1][j+1];
				}
				else dp[i][j+1] = dp[i-1][j+1];
			}
		}
		int ans1=0,ans2=0;
		for(int i=0;i<=N;i++){
			if(dp[N][i].first == ans1){
				if(dp[N][i].second < ans2) ans2 = dp[N][i].second;
			}
			else if(dp[N][i].first > ans1){
				ans1 = dp[N][i].first;
				ans2 = dp[N][i].second;
			}
		}

		cout << "Case " << cou << ":" << endl;
		cout << ans1 << endl;
		cout << ans2 << endl;
	}
}

C++: #include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <map>
#define INF 100000000
#define rep(i,a) for(int i=0;i<(a);i++)

using namespace std;
typedef long long ll;

int dp[2000][20000];    //dp[i][j]  i番目以前の物で、重さがj以下の時の価値
int W[2000],V[2000];

int w,n;

void solve(){
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<=w;j++){
            if(j-W[i]<0){
                dp[i][j]=dp[i+1][j];
            }
            else{
                dp[i][j]=max(dp[i+1][j],dp[i+1][j-W[i]]+V[i]);
            }
            
        }
    }
    
    cout<<dp[0][w]<<endl;
    for(int i=w;i>=1;i--){
        if(dp[0][i]!=dp[0][i-1]){
            cout<<i<<endl;
            break;
        }
    }
}

int main(){
    int count=1;
    while(1){
        memset(dp,0,sizeof(dp));
    
        cin>>w>>n;
        if(w==0)break;
        char a;
        rep(i,n)cin>>V[i]>>a>>W[i];
    
        cout<<"Case "<<count<<":"<<endl;
        count++;
        solve();
    }
    return 0;
}

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

int main(){

	int cnt, N, W, value, weight, v[1001][1001], w[1001][1001];

	cnt = 0;

	while(1){
		cin >> W;
		if(W == 0) break;
		
		cnt++;
		cin >> N;

		for(int i=0; i<=N; i++){
			v[0][i] = 0;
			w[0][i] = 0;
		}
		
		for(int i=1; i<=N; i++){
			scanf("%d, %d", &value, &weight);
			for(int j=0; j<=W; j++){
				if(weight > j){
					v[i][j] = v[i-1][j];
					w[i][j] = w[i-1][j];
				}
				else {
					if(v[i-1][j] < v[i-1][j-weight] + value || (v[i-1][j] == v[i-1][j-weight] + value && v[i-1][j] > w[i-1][j-weight] + weight)){
						v[i][j] = v[i-1][j-weight] + value;
						w[i][j] = w[i-1][j-weight] + weight;
					}
					else {
						v[i][j] = v[i-1][j];
						w[i][j] = w[i-1][j];
					}
				}
			}
		}

		cout << "Case " << cnt << ":" << endl;
		cout << v[N][W] << endl;
		cout << w[N][W] << endl; 
		
	}

	return 0;

}

C++: #include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i = 0 ; i < a; i ++)
int main(void){
  int w;
  int n;
  int num=0;
  while(cin>>w,w){
    cout<<"Case "<<++num<<":"<<endl;
    cin>>n;
    vector<pair<int,int> > in(n);
    rep(i,n){
      int a,b;
      scanf("%d,%d",&a,&b);
      in[i]=make_pair(a,b);
   }    
    int resw = 0;
    int resm = 0;
    int last = 1<<n;
    for(int i = 1 ; i < last+1 ; i ++){
      //cout<<i<<endl;
      int nw = 0;
      int money = 0;
      rep(j,n-1){
	bool use = (i/(1<<j))%2;
	if(use){
	  money += in[j].first;
	  nw += in[j].second;
	}
      }
      if(nw>w)continue;
      if(resm<money){
	//rep(k,n-1)cout<<(i/(1<<k))%2<<" ";
	//cout<<endl;
	  
	resm = money;
	resw = nw;
      }
      if(money==resm && resw<nw){
	resw = nw;
      }
      //cout<<i<<" "<<resw<<endl;
      //cout<<endl;
    }
    cout<<resm<<endl<<resw<<endl;

    //*/
  }
}