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;
/*{{{*/  //template
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define all(v) ALL(v)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
#define CININIT cin.tie(0),ios::sync_with_stdio(false)
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/


void solve(int W,int N){
    vector<int> v(N),w(N);
    char c;
    rep(i,N) cin>>v[i]>>c>>w[i];

    vector<vector<int>> dp(N+10,vector<int>(W+10,0));
    for(int i=0;i<N;i++){
        // use v[i],w[i]
        for(int j=0;j<=W;j++){
            if(j+w[i]<=W){
                dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            }else{
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            }
        }
    }

    for(int i=0;i<=W;i++) if(dp[N][i]==dp[N][W]){
        printf("%d\n%d\n",dp[N][W],i);
        return;
    }
    assert(false);
}

int main(){
    int w,n;
    int cnt=0;
    while(1){
        cin>>w;
        if(w==0) break;
        cin>>n;
        printf("case %d:\n",++cnt);
        solve(w,n);
    }
}

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

int main(){

	int cnt, N, W, value, weight, v[1001][1001], w[1001][1001];

	cnt = 0;

	while(1){
		cin >> W;
		if(W == 0) break;
		
		cnt++;
		cin >> N;

		for(int i=0; i<N; i++){
			for(int j=0; j<W; j++){
				v[i][j] = 0;
				w[i][j] = 0;
			}
		}
		
		for(int i=1; i<=N; i++){
			scanf("%d, %d", &value, &weight);
			for(int j=0; j<=W; j++){
				for(int k=0; k<=j; k++){
					if(w[i-1][k] + weight <= j && v[i-1][k] + value > v[i][j]){
						v[i][j] = v[i-1][k] + value;
						w[i][j] = w[i-1][k] + weight;
					}
					if(v[i-1][k] > v[i][j]){
						v[i][j] = v[i-1][k];
						w[i][j] = w[i-1][k];
					}
				}
			}
		}

		cout << "Case " << cnt << ":" << endl;
		cout << v[N][W] << endl;
		cout << w[N][W] << endl; 
		
	}

	return 0;

}

C++: #include<stdio.h>
int main(void){
    int W,N,v[1000], w[1000], vw[1000], i, j, key, check, sum_v, sum_w;
    scanf("%d %d", &W, &N);
    while ( W ) {
        for ( i = 0; i < N; i++ ) {
            scanf("%d,%d", &v[i], &w[i]);
            vw[i] = v[i] / w[i];
            /*printf("a %d %d\n", N, i);*/
        }
        /*printf("b\n");*/
        check = 1;
        for ( i = 0; check; i++ ) {
            check = 0;
            for ( j = N - 1; j > i; j-- ) {
                if (vw[j] > vw[j - 1] ) {
                    key = vw[j];
                    vw[j] = vw[j - 1];
                    vw[j - 1] = key;
                    key = v[j];
                    v[j] = v[j - 1];
                    v[j - 1] = key;
                    key = w[j];
                    w[j] = w[j - 1];
                    w[j - 1] = key;
                } else if (vw[j] == vw[j - 1] && w[j] < w[j - 1] ) {
                    key = vw[j];
                    vw[j] = vw[j - 1];
                    vw[j - 1] = key;
                    key = v[j];
                    v[j] = v[j - 1];
                    v[j - 1] = key;
                    key = w[j];
                    w[j] = w[j - 1];
                    w[j - 1] = key;
                }
            }
        }
        for ( i = 0; i < N; i++ ) printf("vw%d v%d w%d\n", vw[i], v[i], w[i]);
        sum_v = sum_w = 0;
        for ( i = 0; i < N; i++ ) {
            if ( sum_w + w[i] <= W ) {
                sum_v += v[i];
                sum_w += w[i];
            }
            printf("sum_v%d sum_w%d\n", sum_v, sum_w);
        }
        printf("\n");
        printf("%d\n%d", sum_v, sum_w);
    }
    return 0;
}

C++: #include <iostream>
#include <complex>

typedef std::complex<int> P;
using namespace std;

#define SAFE_DELETE(p) {\
if(p != NULL){\
	delete [] p;\
}\
}

int w,n;
int* item;
int* price;

P dfs(int index, P now)
{
	if(now.real() > w)
	{
		return P(0, -100);
	}
	if(index >= n)
		return now;
	P next = P(now.real()+item[index], now.imag()+ price[index]);
	P a = dfs(index+1, next);
	P b = dfs(index+1, now);
	if(a.imag() > b.imag())
	{
		return a;
	}
	else if(a.imag() < b.imag())
	{
		return b;
	}
	else if(a.real() > b.real())
	{
		return b;
	}
}

int main(int argc, char *argv[]) {
	item = NULL;
	price = NULL;
	int i=1;
	for(;;)
	{
		cin >> w >> n;		
		if(n <= 0)
			return 0;
		SAFE_DELETE(item);
		SAFE_DELETE(price);
		item = new int[n];
		price = new int[n];
		
		char delim = ',';
		for(int i=0; i<n; i++)
		{
			cin >> price[i] >> delim >> item[i];
		}
		P ans = dfs(0, P(0,0));
		cout << "Case "<< i << ":" << endl;
		cout << ans.imag() << endl;
		cout << ans.real() << endl;

		i++;
	}

}