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 <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cfloat>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( v, c ) for ( auto &v : c )

#define ITER( c ) __typeof( (c).begin() )
#define IREP( c, it ) for ( ITER(c) it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int casenum = 1;

	while ( true )
	{
		int w;
		cin >> w;

		if ( !w )
		{
			break;
		}

		int n;
		cin >> n;

		vector< PII > tres( n );
		EACH( tre, tres )
		{
			char dummy;

			cin >> tre.fst >> dummy >> tre.snd;
		}

		VVI dp( n + 1, VI( w + 1, 0 ) );

		REP( i, 0, n )
		{
			REP( j, 0, w + 1 )
			{
				dp[ i + 1 ][j] = max( dp[ i + 1 ][j], dp[i][j] );

				if ( j + tres[i].snd <= w )
				{
					dp[ i + 1 ][ j + tres[i].snd ] = max( dp[ i + 1 ][ j + tres[i].snd ], dp[i][j] + tres[i].fst );
				}
			}
		}

		int resnum = -1, resmax = 0;

		REP( i, 0, w + 1 )
		{
			if ( resmax < dp[n][i] )
			{
				resnum = i;
				resmax = dp[n][i];
			}
		}

		cout << "Case " << casenum++ << ':'<< endl;
		cout << resmax << endl;
		cout << resnum << endl;
	}

	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define FOR(I,F,N) for(int I = F; I < (int)(N); I++)
#define rep(i, n) FOR(i, 0, n)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 28)
 
template<typename T>
void remove(vector<T>& vector, unsigned int index){
vector.erase(vector.begin() + index);
}
 
typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
 
int W, N;
int tres[1001];
int weig[1001];
int maxW, maxV;
int can[1001];
int dp[1001][1001];
 
void dfs(int weight, int value, int index){
	if(can[index] < maxV)return;
    if(weight > W)return;
    if(dp[weight][index]>value)return;
    dp[weight][index] = value;
    if(index == N){
        if(maxV < value){
            maxW = weight;
            maxV = value;
        }else if(maxV == value){
            if(maxW > weight){
                maxW = weight;
                maxV = value;
            }
        }
        return;
    }
    if(dp[weight][index+1]<value)dfs(weight, value, index+1);
    if(weight+weig[index] > W)return;
    if(dp[weight+weig[index]][index+1]<value+tres[index])dfs(weight+weig[index], value+tres[index], index+1);
}
 
 
int main(void){
    int cnt = 0;
    while(cin >> W, W){
        cnt++;
        cin >> N;
        maxW = 0;
        maxV = 0;
        // fill_n(tres, 1001, 0);
        // fill_n(weig, 1001, 0);
        fill_n(*dp, 1001*1001, -1);
 
        rep(i,N){
            int n, w;
            scanf("%d,%d", &n, & w);
            tres[i] = n;
            weig[i] = w;
            if(i==0)can[i]=tres[i];
            else can[i] = can[i-1]+tres[i];
        }
 
        dfs(0,0,0);
        cout << "Case " << cnt << ":" << endl;
        cout << maxV << endl << maxW << endl;
    }
 
    return 0;
}
 
 
 
int StrToInt(string s){
    stringstream ss;
    ss << s;
    int val;
    ss >> val;
    return val;
}
string IntToStr(int i){
    stringstream ss;
    ss << i;
    return ss.str();
}

C++: #include <iostream>
using namespace std;
int main(){
	int W,N;int count=0;
	while(1){
	cin >> W ; count++;
	if(W==0) break;
	cin >> N ;
	int temp[1000][2];char ch;
	for(int i=0;i<N;i++) cin >> temp[i][0] >> ch >> temp[i][1] ;
	//全探索
	int msum_t,wsum_t;int temp_msum=0;int temp_wsum=0;
	for(int k=0;k<N;k++){
	int stack[1000]={0};int ptr=0;int msum=0;int wsum=0;
	for(int i=k;i<N;i++){
		if(wsum+temp[i][1]<W) do{msum+=temp[i][0];wsum+=temp[i][1];stack[ptr++]=i;}while(0);
		else 
			do{for(int j=0;j<ptr;j++){
			msum_t=msum-temp[stack[j]][0]+temp[i][0];
			wsum_t=wsum-temp[stack[j]][1]+temp[i][1];
			if(msum_t>msum && wsum_t<W) do{msum=msum_t;wsum=wsum_t;stack[j]=i;}while(0);
			else if(msum_t==msum && wsum_t<wsum) do{wsum=wsum_t;stack[j]=i;}while(0);
			};
			}while(0);
	};
	if(msum>temp_msum) do{temp_msum=msum; temp_wsum=wsum;}while(0);
	else if(msum==temp_msum && wsum<temp_wsum) temp_wsum=wsum;
	};
	cout << "Case " << count << ":\n" << temp_msum << '\n' << temp_wsum << '\n' ;
	};
}

C++: #include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int mp[1001][1001];

int main(){
	int W;char c;
	for(int num = 0;cin >> W&&W;num++){
		int v[1000], w[1000], n;
		cin >> n;
		fill((int*)mp, (int*)(mp+n+1), 0);
		for(int i = 0;i < n;i++)cin >> v[i] >> c >> w[i];
		for(int i = 0;i < n;i++){
			
			for(int j = 0;j < W+1;j++){
				if(j < w[i])mp[i+1][j] = mp[i][j];
				else mp[i+1][j] = max(mp[i][j], mp[i][j-w[i]]+v[i]);
			}
		}
		
		int ans = 0;
		for(int i = 1;i < W+1;i++){
			if(mp[n][i] > mp[n][ans])ans = i;
		}
		cout << "Case " << num+1 << ":" << endl;
		cout << mp[n][ans] << endl << ans << endl;
	}
	return 0;
}
/*
1
y eazqyp pnop pngtg ye obmpngt xmybp mr lygw
*/