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 <algorithm>
#include <cassert>
#include <vector>
#include <string>
#include <cmath>
#include <map> 
using namespace std;
 
const int MAX= 10000100;

#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define rep(i,a) loop(i,0,a)
#define all(a) (a).begin(),(a).end()
#define MAX_V 1000
#define MAX_W 10000
int W,N;
int dp[MAX_V+1][MAX_W+1];
int w[MAX_W+1];
int v[MAX_V+1];
void solve(){
  int cnt = 0;
  vector<int> data(N,0);
  for(int i = N - 1 ; i >= 0 ; i --){
    
    for(int j = 0 ; j <= W ; j ++){
    data[i]++;
      if(j<w[i]){
	data[i]--;
	dp[i][j] = dp[i+1][j];
      }else {
	dp[i][j] = max(dp[i+1][j] , dp[i+1][j-w[i]] + v[i]);

	if(dp[i+1][j] < dp[i+1][j-w[i]] + v[i]){
	  data[i]--;
	}
      }
    }
  }
  rep(i,5){
    if(data[i]==0){
      cnt+= w[i];
    }
  }
  printf("%d\n",dp[0][W]);
  cout<<cnt<<endl;
}

int main(void){
  int cnt = 0;
  while(cin>>W,W){
    cout<<"Case "<<++cnt<<":"<<endl;
    cin>>N;
    for(int i = 0 ; i < N ; i ++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    solve();
    
  }
  
}

C++: #include <iostream>
#include <string>
#include <vector>
using namespace std;

int wmax, n;
vector<int> v(1000), w(1000);

int main() {
  int cnt = 0;
  while (cin >> wmax >> n) {
    for (int i = 0; i < n; ++i) {
      string tmp;
      getline(cin, tmp, ',');
      v[i] = atoi(tmp.c_str());
      getline(cin, tmp);
      w[i] = atoi(tmp.c_str());
    }

    vector<vector<int>> res(wmax+1, vector<int>(n));

    for (int c=0; c<n; ++c) {
      for (int r=0; r<wmax+1; ++r) {
        if (c==0) {
          res[r][c] = (r < w[0]) ? 0 : v[0];
        }
        else {
          if (r < w[c]) {
            res[r][c] = res[r][c-1];
          }
          else {
            int v1 = res[r][c-1];
            int v2 = res[r-w[c]][c-1] + v[c];
            res[r][c] = (v1 < v2)? v2 : v1;
          }
        }
      }
    }

    int res_v = 0;
    int res_w = wmax;
    for (int r=0; r<wmax+1; ++r) {
      for (int c=0; c<n; ++c) {
        if (res_v < res[r][c]) {
          res_v = res[r][c];
          res_w = r;
        }
      }
    }

    cout << "Case " << ++cnt << ":" << endl;
    cout << res_v << endl;
    cout << res_w << endl;
  }
  return EXIT_SUCCESS;
}

C++: #include<iostream>
#include<stdio.h>
using namespace std;
int dp[1001][1001];
int main(){
  int W,N,v[1000],w[1000];
  int n=1;
  int lastj;
  char jyama;
  while(cin>>W&&W){
    cin>>N;
    for(int i=0;i<N;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    for(int i=0;i<N-1;i++){
      for(int j=0;j<=W;j++){
	if(j<w[i]){
	  dp[i+1][j]=dp[i][j];
	}else{
	  dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
	  if(dp[i+1][j]!=dp[i][j]) lastj=j;
	}
      }
    }
    cout<<"Case "<<n<<":"<<endl;
    cout<<dp[N-1][W]<<endl;
    cout<<lastj<<endl;
  }
}

C++: c[2001],w[2001];
dp[1002][2001];
#define max(a,b) a>b?a:b
N,W,r,x;main(o,i,j){
	for(;scanf("%d%d",&W,&N),W;printf("Case %d:\n%d\n%d\n",o++,r,x),memset(dp,0,sizeof dp)){
		for(r=N;r--;)scanf("%d,%d",c+r,w+r);
		for(i=0;i<=N;i++)for(j=0;j<=W;j++){
			//if(i)dp[i][j]=max(dp[i][j],dp[i-1][j]);
			dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+c[i]);
			if(r<dp[i][j])r=dp[i][j],x=j;
		}
	}
}

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;
    }
  */
  if(kind == treasurea.size() || correntWeight == 0)
    {
      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;

      if(correntWeight - treasurea[i].weight >= 0)
        {
          Treasurea 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>
#include <algorithm>
using namespace std;
const int INF = 1 << 19;
const int W_MAX = 1000;
const int N_MAX = 1000;

int v[N_MAX + 1], w[N_MAX + 1];
int N,W;
int dp[N_MAX + 1][W_MAX +1];//N個目までで、Wを超えないように選んだ時の最大値

int main()
{
	int c = 1;
	while(cin >> W,W){
		cin >> N;
		for(int i = 0; i < N; ++i){
			cin >> v[i]; cin.ignore(1,','); cin >> w[i];
		}
		
		for(int i = 0; i < N; ++i){
			for(int j = 0; j <= W; ++j){
				if(j < w[i]){
					dp[i + 1][j] = dp[i][j];
				}else {
					dp[i + 1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
				}
			}
		}
		cout << "Case " << c++ << ':' << endl;
		int max_v = -1, min_w = INF;
		for(int i = 0; i <= W; ++i){
			if(dp[N][i] > max_v){
				max_v = dp[N][i];
				min_w = i;
			}
		}
		cout << max_v << endl << min_w << endl;
	}
}