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<bits/stdc++.h>
using namespace std;
int dp[1001][1001],wait[1001],value[1001],dpp[1001][40000];
void Initialization()
{
    for(int i=0;i<1001;i++)for(int j=0;j<1001;j++)dp[i][j]=-1;
    for(int i=0;i<1001;i++)for(int j=0;j<50000;j++)dpp[i][j]=-1;
}
int power(int n)
{
    int num=1;
    for(int i=1;i<=n;i++)num*=10;
    return num;
}
int serch(int i,int j,int n)
{
    int num;
    if(dp[i][j]>-1)return dp[i][j];
    else if(i==n)num=0;
    else if(j<wait[i])num=serch(i+1,j,n);
    else num=max(serch(i+1,j,n),serch(i+1,j-wait[i],n)+value[i]);
    return dp[i][j]=num;
}
int wserch(int i,int va,int ser,int n,int w)
{
    int num;
    if(dpp[i][va]>-1)return dpp[i][va];
    else if(i==n)num=w;
    else if(ser<va+value[i])num=wserch(i+1,va,ser,n,w);
    else if(ser==va+value[i])num=wait[i];
    else num=min(wserch(i+1,va,ser,n,w),wserch(i+1,va+value[i],ser,n,w)+wait[i]);
    return dpp[i][va]=num;
}
int main()
{
    int n,w,point,num=1,wai,wa;
    string str;
    while(cin>>w&&w!=0){
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>str;
            value[i]=0;wait[i]=0;
            for(int j=0;;j++){
                if(str[j]==','){
                    for(int k=0;k<j;k++)value[i]+=power(j-k-1)*(str[k]-'0');
                    point=j;
                }
                if(str[j]=='\0'){
                    for(int k=point+1;k<j;k++)wait[i]+=power(j-k-1)*(str[k]-'0');
                    break;
                }
            }
        }
        Initialization();
        point=serch(0,w,n);
        wai=w;
        for(int i=0;i<n;i++){
            if(value[i]<point){
                wa=wserch(i+1,value[i],point,n,w)+wait[i];
                if(wa<wai)wai=wa;
            }
            else if(value[i]==point&&wai>wait[i])wai=wait[i];
        }
        cout<<"Case "<<num<<":\n"<<point<<endl<<wai<<endl;
        num++;
    }
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
using namespace std;

struct Treasure{
	int Weight;
	int Worth;
};
vector<int> TempMaxWorth;

int GetMaxWorth(const int MaxWeight,vector<Treasure> nowTreasureCollection,vector<Treasure>::iterator& nowIterator,const vector<Treasure>& AllTreasureCollection){
	 vector<Treasure>::iterator rootIterator(nowIterator);
	for (; nowIterator!=AllTreasureCollection.end(); ++nowIterator){
		nowTreasureCollection.push_back(*(nowIterator));
		const int NowWorth = accumulate(nowTreasureCollection.cbegin(),
			nowTreasureCollection.cend(),
			0,
			[](const int q, const Treasure& p){return q + p.Worth; }
		);
		const int NowWeight = accumulate(nowTreasureCollection.cbegin(),
			nowTreasureCollection.cend(),
			0,
			[](const int q, const Treasure& p){return q + p.Weight; });
		if (NowWeight <= MaxWeight&&NowWorth > TempMaxWorth[NowWeight]){
			TempMaxWorth[NowWeight] = NowWorth;
			replace_if(TempMaxWorth.begin() + NowWeight, TempMaxWorth.end(), [=](int n){return NowWorth > n; }, NowWorth);
			if((++nowIterator)!=AllTreasureCollection.end())GetMaxWorth(MaxWeight, nowTreasureCollection, nowIterator,AllTreasureCollection);
			nowIterator--;
		}
		nowTreasureCollection.pop_back();
	}
	((nowIterator)) = (rootIterator);
	return 0;
}

int main(){
	int MaxWeight;
	int TreasureNum;
	for (int i = 1; cin >> MaxWeight;++i){
		if (MaxWeight == 0)return 0;
		cin  >> TreasureNum;
		TempMaxWorth.resize(MaxWeight + 1);
		fill(TempMaxWorth.begin(), TempMaxWorth.end(), 0);
		vector<Treasure> AllTreasureCollection;
		for (int j = 0; j < TreasureNum; ++j){
			Treasure T;
			cin >> T.Worth;
			cin.get();
			cin >> T.Weight;
			AllTreasureCollection.push_back(T);
		}	
		vector<Treasure> NowTreasureCollection = {};
		GetMaxWorth(MaxWeight, NowTreasureCollection, AllTreasureCollection.begin(), AllTreasureCollection);
		cout << "Case " << i << " :" << endl << TempMaxWorth[MaxWeight] << endl << find(TempMaxWorth.cbegin(), TempMaxWorth.cend(), TempMaxWorth[MaxWeight]) - TempMaxWorth.cbegin() << endl;
	}
	return 0;
}

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

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

int main(){
	int W, cnt=1;
	while( scanf("%d",&W), W ){
		int n, v[1000], w[1000], dp[1001];
		scanf("%d", &n);
		rep(i,n){
			scanf("%d,%d", &v[i], &w[i]);
		}
		rep(i,W)	dp[i+1] = -1;
		dp[0] = 0;
		rep(i,n){
			for(int j=W; j>=0; j--){
				if( dp[j] != -1 && j+w[i]<=W ){
					dp[j+w[i]] = max( dp[j+w[i]], dp[j]+v[i] );
				}
			}
		}
		int mw = 0;
		rep(i,W){
			if( dp[i]>dp[mw] )	mw = i;
		}
		printf("Case %d:\n",cnt++);
		printf("%d\n", dp[mw]);
		printf("%d\n", mw);
	}
}

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

using namespace std;

#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,-1,sizeof(a))

int W, n;
int v[1002], w[1002];
int dp[1002][1002];

int rec(int i, int j) {
    if(dp[i][j] >= 0) return dp[i][j];

    int res = 0;
    if(i == n) {
        res = 0;
    } else if(j < w[i]) {
        res = rec(i+1, j);
    } else {
        res = max(rec(i+1,j), rec(i+1, j-w[i]) + v[i]);
    }

    return dp[i][j] = res;
}

int main() {
    for(int data = 1; ; data++) {
        ZERO(v); ZERO(w); MINUS(dp);
        scanf("%d", &W);
        if(W == 0) break;
        scanf("%d", &n);
        for(int i=0; i<n; i++) scanf("%d,%d", v+i, w+i);

        int ans = rec(0, W), wret = W;
        while(dp[0][wret] == ans) wret--;
        printf("Case %d:\n", data);
        printf("%d\n", ans);
        printf("%d\n", wret);
    }
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define fr first
#define sc second
using namespace std;

int w,n;
typedef pair<int,int> P;
P dp[1001][1001];
bool chg[1001][1001];
vector <P> dat;

P rec(int idx,int wi){
    P ans;
    if(chg[idx][wi]) return dp[idx][wi];
    if(idx == n){
        ans = P(0,wi);
    }
    else{
        if(wi - dat[idx].sc >= 0){
            P p = rec(idx+1,wi-dat[idx].sc);
            p.first += dat[idx].fr;
            ans = max(p,rec(idx+1,wi));
        }
        else ans = rec(idx+1,wi);
    }
    chg[idx][wi] = true;
    return dp[idx][wi] = ans;
}

int main(){
    while(cin >> w,w){
        int a = 0;
        memset(dp,-1,sizeof(dp));
        memset(chg,false,sizeof(chg));
        cin >> n;
        for(int i=0;i<n;i++){
            int t,m; scanf("%d,%d",&t,&m); dat.push_back(P(t,m));
        }
        P p = rec(0,w);
        cout << "Case " << ++a << ":\n" << p.fr << endl << w - p.sc << endl;
        dat.resize(0);
    }
}