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 <algorithm>
#include <vector>

#define min(a,b) {a > b ? b:a}
#define max(a,b) {a > b ? a:b}
using namespace std;

#define MAX_W 1000
#define MAX_N 1000

int dp[MAX_W + 1];
void q42() {
	int W, N;
	int cnt = 1;
	for (; cin >> W;) {
		if (!W) break;

		cin >> N;
		vector<pair<int, int> > Item;
		for (int i = 0; i < N; i++) {
			int value, weight;
			char tmp;
			cin >> value >> tmp >> weight;
			Item.push_back(make_pair(value, weight));
		}

		for (int i = 0; i <= W; i++) {
			dp[i] = -1;
		}
		dp[0] = 0;

		for (int i = 0; i < N; i++) {
			int value = Item[i].first;
			int weight = Item[i].second;
			for (int j = W; j >= 0; j--) {
				if (j - weight < 0) continue;
				if (dp[j - weight] == -1) continue;
				dp[j] = max(dp[j], dp[j - weight] + value);
			}
		}

		int ans_value = 0, ans_weight = 0;
		for (int i = 0; i <= W; i++) {
			cout << dp[i] << endl;
			if (ans_value < dp[i]) {
				ans_value = dp[i];
				ans_weight = i;
			}
		}

		cout << "Case " << cnt++ << ":" << endl;
		cout << ans_value << endl;
		cout << ans_weight << endl;
	}
}

int main() {
	q42();
	return 0;
}

C++: // dpの練習
// dpでなく、愚直に組んだプログラミング
// ナップサック問題とほぼ同じ

#include <iostream>
#include <algorithm>

using namespace std;

int wei; // 持てる最大の重さ
int n; // お宝の数
int v[1001]; // お宝の価値
int w[1001]; // お宝の重さ
 // グローバル配列は0で初期化されている

int max_value(int i, int j) {
  int value;
 
  if (i == n) {
    // 品物がもう残っていないときは、価値の和の最大値は0で確定
    //もうお宝がないつまり、価値は0
    value = 0;
  } else if (j < w[i]) {
    //風呂敷が持てる重さを超えてしまう
    // 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理
    // i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする
    value = max_value(i + 1, j);
  } else {
    //左がお宝を入れない、右がお宝を入れた場合
    // 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ
    value = max( max_value(i + 1, j), max_value(i + 1, j - w[i]) + v[i] );
  } 
  return value;
}

int max_weight(int i, int j) {
  int weight;
 
  if (i == n) {
    // 品物がもう残っていないときは、価値の和の最大値は0で確定
    //もうお宝がないつまり、価値は0
    weight = 0;
  } else if (j < w[i]) {
    //風呂敷が持てる重さを超えてしまう
    // 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理
    // i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする
    weight = max_weight(i + 1, j);
  } else {
    //左がお宝を入れない、右がお宝を入れた場合
    // 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ
    weight = max( max_weight(i + 1, j), max_weight(i + 1, j - w[i]) + w[i] );
  } 
  return weight;
}


int main(void){

  int cnt = 1;
  while( cin >> wei ){
    if( wei == 0 )break;
    cin >> n;
    char ten;
    for( int i = 0 ; i < n ; i++ ){
      cin >> v[i] >> ten >> w[i];
    }
    cout << "Case " << cnt << ":" << endl;
    cout << max_value(0,wei) << endl;
    cout << max_weight(0,wei)-1 << endl;
    cnt++;
  }
  return 0;
}

C++: #include <bits/stdc++.h>

#define FOR(i, n, m) for(int i = (n);i < (m);i++)
#define REP(i, n) for(int i = 0;i < (n);i++)
#define PII pair<int, int>

typedef long long int lli;

using namespace std;

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

int main(void){
    int cs = 1;
    while(cin >> W && W){
        int dp[1000+1][1000+1] = {};
        cin >> n;
        REP(m, n){
            int a, b;
            scanf("%d, %d", &a, &b);
            v.push_back(a);
            w.push_back(b);
        }

        FOR(i, 1, n+1){
            FOR(j, 0, W+1){
                if(j < w[i-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
                }
            }
        }

        cout << "Case " << cs << ":" << endl;
        cout << dp[n][W] << endl;
        int min_w = 100000000;
        REP(j, W+1){
            if(dp[n][j] == dp[n][W])
                min_w = min(min_w, j);
        }
        cout << min_w << endl;
        cs++;
    }
    return 0;
}