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++: //AOJ0042.cpp created 8 28, 2015

#include <iostream>
#include <algorithm>
#include <cstdio>
const int MAX_N = 1000;
const int MAX_W = 1000;

struct status{
    int weight;
    int value;
}st[MAX_N];

struct status ini={-1,-1};
struct status dp[MAX_N+1][MAX_W+1];
int n,stweight;

struct status val(int i,int j){
    if(dp[i][j].value!=-1) return dp[i][j];
    status retv;
    if(i==n){
        retv.value=0;
        retv.weight=0;
    }else if(j<st[i].weight){
        retv=val(i+1,j);
    }else{
        status add,nadd;
        nadd = val(i+1,j);
        add = val(i+1,j-st[i].weight);
        add.value +=st[i].value;
        retv.value = std::max(add.value,nadd.value);
        //retv=std::max(val(i+1,j),val(i+1,j-st[i].weight)+st[i].value);
        if(add.value == nadd.value) retv.weight=std::min(add.weight+st[i].weight,nadd.weight);
        else if(add.value>nadd.value) retv.weight = add.weight+st[i].weight;
        else retv.weight = nadd.weight;
    }
    return dp[i][j]=retv;
}

int main() {
    int no=1;
    while(std::cin >> stweight,stweight!=0){
        std::cin >> n;
        for(int i=0;i<MAX_N;i++)
            for(int j=0;j<MAX_W;j++)
                dp[i][j]=ini;
        for(int i=0;i<n;i++){
            scanf("%d,%d",&(st[i].value),&(st[i].weight));
        }
        struct status ans = val(0,stweight);
        std::cout <<"Case "<< no++ << ":" << std::endl << ans.value << std::endl << ans.weight << std::endl;
        
    }
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std ;

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int w,n;
  int cnt = 1;
  char c;
  while(cin >> w){
    if(w == 0) break;
    cin >> n;
    vary(int,vs,n,0);
    vary(int,ws,n,0);
    vector<vector<int>> dp(n+1,vector<int>(w+1,0));
//     vector<vector<int>> dp2(n+1,vector<int>(w+1,0));
    rep(i,n){
      cin >> vs[i] >> c >> ws[i];
    }
    REP(i,0,n){
      rep(j,w){
        dp[i+1][j] = max(dp[i][j], j-ws[i] >= 0? dp[i][j-ws[i]]+ vs[i] : 0);
      }
    }
    cout << "Case " + to_string(cnt) + ":"<<endl;
    rep(i,w+1){
      if(dp[n][i] == dp[n][w-1]){
        cout << dp[n][w-1]<<endl<<i<<endl;
        break;
      }
    }
    ++cnt;
  }
  return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
// #define first first
// #define second se
using namespace std;
typedef pair<int, int> P;
typedef vector<int> vi;

int dp[1100][1100];

signed main(){
    int W;
    int cnt = 0;
    while(cin >> W, W){
        int n;
        cin >> n;
        cnt++;
        vector<int> v(n), w(n);
        rep(i, 0, n){
            char c;
            cin >> v[i] >> c >> w[i];
        }
        rep(i, 0, 1010){
            rep(j, 0, 1010){
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 0;
        rep(i, 0, n){
            rep(j, 0, W + 1){
                if(j - w[i] >= 0){
                    dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
                }
            }
        }
        int ans = -1, wt = 0;
        rep(i, 0, W + 1){
            if(dp[n][i] > ans){
                ans = dp[n][i];
                wt = i;
            }
        }
        cout << "Case " << cnt << ":" << endl;
        o(ans);
        o(wt);
    }
}