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 <algorithm>
#include <vector>


using namespace std;

typedef struct{
    int weight;
    int value;
} treasure;

typedef struct{
    int value;
    bool flag[1001];
} thief;

int main(void){
    int w,n,cs=0;
    thief h[1001];
    treasure tr[1001];


    while(true){
        cin>>w;
        if(w==0) break;
        cs++;
        cin>>n;

        for(int i=0;i<1001;i++){
            h[i].value=0;
            for(int j=0;j<1001;j++){
                h[i].flag[j]=false;
            }
        }

        for(int i=0;i<n;i++){
            int w,v;
            scanf("%d,%d",&v,&w);
            tr[i].weight=w;
            tr[i].value=v;
        }

        for(int i=1;i<=w;i++){
            for(int j=0;j<n;j++){
                if(i>=tr[j].weight && !h[i-tr[j].weight].flag[j] && h[i-tr[j].weight].value+tr[j].value){
                    h[i].value=h[i-tr[j].weight].value+tr[j].value;
                    h[i].flag[j]=true;
                }
            }
        }

        int max_w;

        for(max_w=w;max_w>1 && h[max_w].value==h[max_w-1].value;max_w--);

        cout<<"Case "<<cs<<":"<<endl;
        cout<<h[w].value<<"\n"<<max_w<<endl;
    }

    return 0;
}

C++: #include <string>
#include <cstring>
#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;

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

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 <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()

#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,a,b) for(int i=(a); i<(b); i++)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int IMAX=((1<<30)-1)*2+1;
const double EPS=1e-10;
//int mod=1000000007


int w,n;
vector<vi> v(1010,vi(1010,-1));
vector<pii> p(1010,pii(0,0));

void init(){
	rep(i,1010){
		rep(j,1010){
			v[i][j]=-1;
		}
	}
}

int calc(int i,int j){
	if(i>=n)return 0;
	if(v[i][j]!=-1)return v[i][j];
	int ret;
	if(j-p[i].se<0)ret=calc(i+1,j);
	else {
		ret=max(calc(i+1,j),p[i].fi+calc(i+1,j-p[i].se));
	}

	// rep(i,n){
	// 	rep(j,w+1){
	// 		printf("%3d ",v[i][j]);
	// 	}
	// 	cout<<endl;
	// }
	// cout<<endl;


	return v[i][j]=ret;
}

int main(){
	char c;
	int Case=0;
	int a,b;
	while(cin>>w && w>0){
		init();
		cin>>n;
		rep(i,n){
			cin>>p[i].fi>>c>>p[i].se;
		}
		a=calc(0,0);
		for(int i=1; i<=w; i++){
			//init();
			if(a<calc(0,i)){
				a=calc(0,i);
				b=i;
			}
		}
		
		cout<<"Case "<<(++Case)<<":"<<endl;
		cout<<a<<endl;
		cout<<b<<endl;
		
	}
}

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

struct treasure{
	int val;
	bool combi[1000];
};

treasure dp[1001][1001];
int main(){
	int w, n;
	for (int dataset = 1; cin >> w, w; dataset++){
		cin >> n;
		for (int i = 0; i <= n; i++){
			for (int j = 0; j < w; j++){
				dp[i][j].val = -1;
				for (int k = 0; k < n; k++){
					dp[i][j].combi[k] = false;
				}
			}
		}
		dp[0][0].val = 0;
		int t_w[1000], t_val[1000], ans_val = 0, ans_w = 0;
		for (int i = 0; i < n; i++){
			scanf("%d,%d", &t_val[i], &t_w[i]);
		}
		for (int i = 0; i <= n; i++){
			for (int j = 0; j < w; j++){
				if (dp[i][j].val == -1) continue;
				if (dp[i][j].val > ans_val){
					ans_val = dp[i][j].val;
					ans_w = j;
				}
				for (int k = 0; k < n; k++){
					if (dp[i][j].combi[k] || j + t_w[k] >= w
						|| dp[i + 1][j + t_w[k]].val > dp[i][j].val + t_val[k])
						continue;
					dp[i + 1][j + t_w[k]] = dp[i][j];
					dp[i + 1][j + t_w[k]].val = dp[i][j].val + t_val[k];
					dp[i + 1][j + t_w[k]].combi[k] = true;
				}
			}
		}
		printf("Case %d:\n%d\n%d\n", dataset, ans_val, ans_w);
	}
	return 0;
}