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<cstdio>
#include<cstring>
#include<vector>

using namespace std;

int N,W;

struct Treasurea
{

  int value;
  int weight;
  int flag;

  Treasurea()
  {
    value = 0;
    weight = 0;
    flag = false;
  }

};

struct Memo
{

  Treasurea record;
  bool flag;

  Memo()
  {
    record.value = 0;
    record.weight = 0;
    record.flag = false;
    flag = false;
  }

};

Memo memo[1001][1001];

Treasurea knapsack(vector<Treasurea> &treasurea, int correntWeight,int correntValue, int kind)
{

  if(correntWeight < 0)
    {
      Treasurea temp;
      temp.weight = W - (correntWeight + treasurea[kind - 1].weight);
      temp.value = correntValue - treasurea[kind - 1].value;
      return temp;
    }
  else if(kind == treasurea.size())
    {
      Treasurea temp;
      temp.weight = W - correntWeight;
      temp.value = correntValue;
      return temp;
    }
  else if(memo[correntWeight][kind].flag) return memo[correntWeight][kind].record;

  Treasurea total;

  for(int i = 0;i < treasurea.size(); ++i)
    {

      if(treasurea[i].flag) continue;

      treasurea[i].flag = true;

      //Treasurea temp = knapsack(treasurea,correntWeight - treasurea[i].weight,correntValue + treasurea[i].value,i + 1);

      Treasurea temp;

      if(correntWeight -treasurea[i].weight < 0) temp = knapsack(treasurea,correntWeight,correntValue,i + 1);
      else temp = knapsack(treasurea,correntWeight - treasurea[i].weight,correntValue + treasurea[i].value,i + 1);

      if(total.value < temp.value || (total.value == temp.value && total.weight > temp.weight))
        total = temp;

      treasurea[i].flag = false;

    }

  memo[correntWeight][kind].record = total;
  memo[correntWeight][kind].flag = true;

  return total;

}

int main()
{

  int case_number = 0;

  while(cin >> W && W != 0)
    {

      cin >> N;

      vector<Treasurea> treasurea(N);
      Treasurea result;

      for(int i = 0; i < N; ++i) scanf("%d,%d",&treasurea[i].value,&treasurea[i].weight);

      memset(memo,0,sizeof(memo));

      result = knapsack(treasurea,W,0,0);

      cout << "Case " << ++case_number << ":"<< endl << result.value << endl << result.weight << endl;

    }

  return 0;

}

C++: #include<iostream>
#define MAX_N 1001
#define MAX_W 1001
using namespace std;


int dp[MAX_N][MAX_W];
int n,W;
int w[MAX_N];
int v[MAX_N];

void solve(){
  memset(dp,0,sizeof(dp));
  cout<<"Case 1:"<<endl;
  for(int i=0;i<n;i++){
    for(int j=0;j<=W;j++){
      if(j>=w[i]){
	dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
      }else{
	dp[i+1][j]=dp[i][j];
      }
    }
  }
  cout << dp[n][W] << endl;
  int tmp=0;
  int weight;
  for(int i=0;i<=W;i++){
    if(dp[n][i]>tmp){
      tmp=dp[n][i];
      weight=i;
    }
  }
cout << weight << endl;
}

int main(){
  while(cin>>W,W){
    cin>>n;
    for(int i=0;i<n;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    solve();
  }

  return 0;
}

C++: #define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>

using namespace std;

typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;

int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

static const double EPS = 1e-8;

int v[1000];
int w[1000];
int dp[1001][1001];

int main(){
	int W,N;
	int idx = 1;
	while(~scanf("%d",&W)){
		if(W==0) break;
		memset(dp,0,sizeof(dp));

		scanf("%d",&N);
		
		for(int i=0;i<N;i++){			
			scanf("%d,%d",&v[i],&w[i]);
		}

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

		int resv = 0;
		int resw = 0;
		for(int j=0;j<=W;j++){
			if(dp[N][j] > resv){
				resv = dp[N][j];
				resw = j;
			}
		}

		printf("Case %d:\n%d\n%d\n",idx++,resv,resw);
	}
}

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<pii>> dp(n+1,vector<pii>(w+1,make_pair(0,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+1){
        if(j <ws[i]){
          dp[i+1][j] = dp[i][j];
//           dp2[i+1][j] = dp2[i][j];
        }
        else{
          pii tmp;
          if(dp[i][j].fi < dp[i][j-ws[i]].fi+vs[i] && j != w){
            int k = dp[i][j-ws[i]].fi+vs[i];
            tmp = make_pair(k,j);
          }
          else{
            tmp = dp[i][j];
          }
          dp[i+1][j] = tmp;
//           dp2[i+1][j] = max(dp2[i][j],dp2[i][j-ws[i]]+vs[i]);
        }
      }
    }
    cout << "Case " + to_string(cnt) + ":"<<endl;
    cout << dp[n][w-1].fi <<endl;
    cout << dp[n][w-1].se <<endl;
    ++cnt;
  }
  return 0;
}