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<vector>
#include<algorithm>
using namespace std;
int w[1000],v[1000];
int W,N;
int memo[1001][1001];
int func(int i,j){
    if(memo[i][j]>=0)return memo[i][j];
    
    int res;
    if(i==N)res=0;
    else if(j-w[i]<0)res=func(i+1,j);
    else res=max(func(i+1,j),func(i+1,j-w[i])+v[i]);
    
    return memo[i][j]=res;
}
int main(){
    int cnt=0;
    while(cin>>W,W){
        cin>>N;
        cnt++;
        for(int i=0;i<N;i++)(cin>>v[i]).ignore()>>w[i];
        fill(memo[0],memo[0]+1001*1001,-1);
        memo[0][0]=0;
        func(0,W);
        
        for(int i=W;i>=0;i--){
            if(memo[0][i]==-1)continue;
            if(memo[0][i]>memo[0][i-1]){
                cout<<"Case "<<cnt<<":"<<endl;
                cout<<memo[0][i]<<endl<<i<<endl;
                break;
            }
        }
    }
    return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
#define LATTE 1000000000
using namespace std;
int W,N,w[1001],v[1001],ansW=LATTE,ansV=0;
int memo[1001][1001],cou,ans2;
int func(int i,int j,int _v){
    //printf(" %d,%d,%d\n",i,j,_v);
    if(j>W)return 0;
    if(memo[i][j]>_v){
        return 0;
    }
    memo[i][j] = _v;
    if(i==N){
        if(ansV<_v){
            ansV = _v;
            ansW = j;
        }
        else if(ansV==_v && ansW>j){
            ansV = _v;
            ansW = j;
        }
        return _v;
    }
    //ans2=max(ans2,j);
    return max(func(i+1,j,_v),func(i+1,j+w[i],_v+v[i]));
    //ans2=max(ans2,j);
}
int main(){
    int tc=1;
    while(cin>>W,W){
        int ans=0,cou=0;
        cin>>N;
        for(int i=0;i<N;i++){
            scanf("%d,%d",&v[i],&w[i]);
        }
        func(0,0,0);
        cout<<"Case "<<tc<<":"<<endl<<ansV<<endl<<ansW<<endl;;
        tc++;
    }
}

C++: #define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int wight, n;
    int cnt = 0;
    while (cin >> wight, wight)
    {
        cin >> n;
        int v[n + 1], w[n + 1];
        char c;
        for (int i = 1; i <= n; i++)
            cin >> v[i] >> c >> w[i];

        int dp[n + 1][wight + 1];
        rep(i, n + 1) rep(j, wight + 1) dp[i][j] = 0;

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

        int m = dp[n][wight];
        cnt++;
        cout << "Case " << cnt << ":" << endl;
        OP(m);
        rep(i, wight + 1)
        {
            if (m == dp[n][i])
            {
                OP(i);
                break;
            }
        }
    }
    return 0;
}

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

int main(){
    int w, n;
    int count = 0;
    while(cin >> w, w){
        vector<pair<int, int> > v;
        long long dp[1010][1010];
        memset(dp, 0, sizeof(dp));
        cin >> n;
        for(int i=0; i < n; i++){int s, t; scanf("%d,%d", &s, &t); v.push_back(make_pair(s, t));}
        for(int i=n-1; 0 <= i; i--){
            for(int j=0; j <= w; 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);
            }
        }
        cout << "Case " << ++count << ":" << endl;
        cout << dp[0][w] << endl;
        for(int i=w; ; i--){
            if(dp[0][i] != dp[0][w]){cout << i+1 << endl; break;}
        }
    }
}

C++: #include <cstdio>

using namespace std;

void rec(int n, int w, int &v, int &rw,
        const int W, const int N,
        const int lv[], const int lw[])
{
    v = rw = 0;
    if (n == N) {
        // not remain any treasure
        v = 0;
        rw = w;
    } else if (w < lw[n]) {
        // cannot pack treasure[n]
        rec(n + 1, w, v, rw, W, N, lv, lw);
    } else {
        int v1, v2, w1, w2;

        // through treasure[n]
        rec(n + 1, w        , v, rw, W, N, lv, lw);
        v1 = v;
        w1 = rw;
        // pack treasure[n]
        rec(n + 1, w - lw[n], v, rw, W, N, lv, lw);
        v2 = v + lv[n];
        w2 = rw - lw[n];

        // which is good
        if (v1 > v2) {
            v = v1;
            rw = w1;
        } else if (v1 < v2) {
            v = v2;
            rw = w2;
        } else {
            if (w1 >= w2) {
                v = v1;
                rw = w1;
            } else {
                v = v2;
                rw = w2;
            }
        }
    }
    // printf("  (%d, %d, %d, %d) -> (%d, %d)\n", n, w, v, rw, v, rw);
}

int dp_v[1000][1000];
int dp_rw[1000][1000];

void rec_dp(int n, int w, int &v, int &rw,
        const int W, const int N,
        const int lv[], const int lw[])
{
    // memo'd
    if (dp_v[n][w] != 0 && dp_rw[n][w] != 0) {
        v = dp_v[n][w];
        rw = dp_rw[n][w];
        return;
    }

    v = rw = 0;
    if (n == N) {
        // not remain any treasure
        v = 0;
        rw = w;
    } else if (w < lw[n]) {
        // cannot pack treasure[n]
        rec_dp(n + 1, w, v, rw, W, N, lv, lw);
    } else {
        int v1, v2, w1, w2;

        // through treasure[n]
        rec_dp(n + 1, w        , v, rw, W, N, lv, lw);
        v1 = v;
        w1 = rw;
        // pack treasure[n]
        rec_dp(n + 1, w - lw[n], v, rw, W, N, lv, lw);
        v2 = v + lv[n];
        w2 = rw - lw[n];

        // which is good
        if (v1 > v2) {
            v = v1;
            rw = w1;
        } else if (v1 < v2) {
            v = v2;
            rw = w2;
        } else {
            if (w1 >= w2) {
                v = v1;
                rw = w1;
            } else {
                v = v2;
                rw = w2;
            }
        }
    }
    // printf("  (%d, %d, %d, %d) -> (%d, %d)\n", n, w, v, rw, v, rw);
    dp_v[n][w] = v;
    dp_rw[n][w] = rw;
}

int main()
{
    for (int icase = 1;; ++icase) {
        int W, N;
        scanf("%d", &W);
        if (W == 0)
            break;
        scanf("%d", &N);

        int v[1000], w[1000];
        for (int i = 0; i < N; ++i)
            scanf("%d,%d", &v[i], &w[i]);

        int retv, retw;
        rec_dp(0, W, retv, retw, W, N, v, w);

        printf("Case %d:\n%d\n%d\n", icase, retv, (W - retw) / 2);
    }

    return 0;
}