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];
int power(int n)
{
    int num=1;
    for(int i=1;i<=n;i++)num*=10;
    return num;
}
int main()
{
    int n,w,point,num=1,wa=0;
    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;
                }
            }
        }point=0;
        memset(dp,0,sizeof(dp));
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<=w;j++){
                if(j<wait[i])dp[i][j]=dp[i+1][j];
                else dp[i][j]=max(dp[i+1][j],dp[i+1][j-wait[i]]+value[i]);
            }
        }
        for(int i=n-1;i>=0;i--){
            if(point<dp[i][w])wa+=wait[i];
            point=dp[i][w];
        }
        cout<<"Case "<<num<<":\n"<<dp[0][w]<<endl<<wa<<endl;
        num++;
    }
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int DP[1001][1001];
int main(){
	int W,N;
	int C=0;
	while(cin>>W){
		if(!W)break;
		cin>>N;
		int v[1000],w[1000],SUMW;
		for(int i=0;i<N;++i) scanf("%d,%d",&v[i],&w[i]);
		for(int i=0;i<=N;++i) DP[0][i]=0;
		for(int i=1;i<=N;++i){
			for(int j=0;j<=W;++j){
				if(w[i]>j){//入らない時
					DP[i][j]=DP[i-1][j];
				}else{//入る時
					DP[i][j]=max((DP[i-1][j]),(DP[i-1][j-w[i]]+v[i]));
				}
			}
		}
		SUMW=W;
		for(int j=W;j>=0;--j) for(int i=N;i>=0;--i) if(DP[N][W]==DP[i][j])SUMW=j;
		cout<<"case "<<++C<<":\n";
		cout<<DP[N][W]<<"\n"<<SUMW<<"\n";
	}
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<string>

using namespace std;

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

int w,n;
vector<int> v;
vector<int> g;

void init(){
	v.clear();
	g.clear();
}
bool input(){
	cin>>w;
	if(w==0)return false;
	cin>>n;
	
	rep(i,n){
		int a,b;
		scanf("%d,%d",&a,&b);
		v.push_back(a);
		g.push_back(b);
	}
	return true;
}

const int W = 1111;
const int N = 1111;
const int INF = 1000000000;
int dp[N][W];

pair<int,int> solve(){
	rep(i,N)rep(j,W)dp[i][j]=0;
	
	reps(i,g[0],w+1)dp[0][i]=v[0];
	
	reps(i,1,n){
		rep(j,w+1){
			if(j!=0)dp[i][j] = dp[i-1][j];
			dp[i][j] = max(dp[i][j],dp[i-1][j]);
			if(j-g[i]>=0)dp[i][j] = max(dp[i][j], dp[i-1][j-g[i]]+v[i]);
		}
	}
	
	int maxp = 0;
	rep(j,w+1){
		if(dp[n-1][maxp]<dp[n-1][j])maxp=j;
	}
	
	/*
	rep(i,n){
		rep(j,w+1)printf("%3d ",dp[i][j]);puts("");
	}*/
	
	return pair<int,int>(dp[n-1][maxp],maxp);
}
int main(){
	for(int i=1;init(),input();i++){
		pair<int,int> ans = solve();
		printf("Case %d:\n%d\n%d\n",i,ans.first,ans.second);
	}
}

/*
10
5
60,2
100,4
120,6
210,9
10,1
0


10
2
100,5
90,4
0

*/

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

const int INF = 1 << 29;
typedef pair<int, int> P;

int n, w;
int dp[1001][1001];//お宝の番号、重さ
int main(void)
{
	int caseCount = 0;
	while(cin >> w && w)
	{
		cin >> n;
		vector<int> ps(n), ws(n);
		memset(dp, 0, sizeof(dp));
		char c;
		for (int i = 0; i < n; i++)
		{
			cin >> ps[i] >> c >> ws[i];
		}

		if(ws[0] <= w) dp[0][ws[0]] = ps[0];
		for (int i = 1; i < n; i++)
		{
			for (int j = 0; j <= w; j++)
			{
				/*if(ws[i] <= j)
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - ws[i]] + ps[i]);*/
				if(j + ws[i] <= w)
					dp[i][j + ws[i]] = max(dp[i][j], max(dp[i - 1][j + ws[i]], dp[i - 1][j] + ps[i]));
				else dp[i][j] = max(dp[i - 1][j], dp[i][j]);
			}
		}

		cout << "Case " << ++caseCount << ":" << endl;
		int ansp = 0, answ = INF;
		for (int i = 0; i <= w; i++)
		{
			if(ansp < dp[n - 1][i])
			{
				ansp = dp[n - 1][i];
				answ = i;
			}
		}
		cout << ansp << endl << answ << endl;
	}
	return 0;
}

C++: //0042 A Thief
//vñFibvTbNâè

#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;

int main(void)
{

	const int MAX_WEIGHT = 1000;
	const int MAX_OBJECT = 10000;
	const int MAX_SCORE = 1000;

	struct Obj
	{
		int w;
		int score;
	};
	struct Cloth
	{
		int index;
		int totalScore;
	};

	int caseNum = 1;
	while(1)
	{
		//ÇÌd³ÌÆ«àAÅãÉüê½CfbNXA»êÜÅÌ¿lð¶ÝµÈ¢lÉ
		int totalScore[MAX_WEIGHT+1] = {0};
		int intoIndex[MAX_WEIGHT+1];	//ÔÁ¿á¯±êÍú»µÈ­ÄàâèÈµ

		//\¢Ì¶áfobOÅl©êÈ¢æI
		//Cloth total[MAX_WEIGHT+1];

		Obj obj[MAX_OBJECT];

		int w, n;
		int i, j;
		char dummy;

		cin >> w;
		if(w == 0)
			break;
		cin >> n;

		for(i = 0; i < n; i++)
		{
			cin >> obj[i].score >> dummy >> obj[i].w;
			
			for(j = w-obj[i].w; j >= 1; j--)
			{
				//·ÅÉ»Ìd³ÜÅÏÜê½àÌª é
				if(totalScore[j])
				{
					//æèæ¢ÂÝûð­©
					if(totalScore[j+ obj[i].w] < totalScore[j] + obj[i].score)
					{
						totalScore[j+ obj[i].w] = totalScore[j] + obj[i].score;
						intoIndex[j+ obj[i].w] = i;
					}
				}
			}
			//ÅÌÍüêÄà¢¢Ìæ
			if(totalScore[obj[i].w] < obj[i].score)
			{
				totalScore[obj[i].w] = obj[i].score;
				intoIndex[obj[i].w] = i;
			}
		}

		cout << "Case " << caseNum << ":" << endl;
		caseNum++;

		//zñÉüÁ½vfÌÅålÆA»ÌCfbNXðT·
		int maxScore = 0;
		int maxIndex = -1;
		for(i = 0; i <= w; i++)
		{
			if(totalScore[i] && maxScore<totalScore[i])
			{
				maxScore = totalScore[i];
				maxIndex = i;
			}
		}
		//½©vfÍüÁÄ½H
		if(maxIndex >= 0)
		{
			cout << totalScore[maxIndex] << endl;

			//d³aÌvZ
			int totalW = 0;
			int index = maxIndex;
			while(index>0)
			{
				totalW += obj[ intoIndex[index] ].w;
				index -= obj[ intoIndex[index] ].w;
			}
			cout << totalW << endl;
		}
		//êÂàüçÈ©Á½H
		else
			cout << "0" << endl << "0" << endl;
	}
	return 0;
}