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<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

string str;

int main()
{
  int w,n;
  int i=1,j,k;
  int max_value[1001][1001];
  int value,weight;

  while(1){
    cin>>w;
    if(w==0)break;
    cin>>n;
   
    rep(j,1001)
      rep(k,1001)
      max_value[j][k]=-1;

    max_value[0][0]=0;

    for(j=1;j<=n;j++){
      scanf("%d,%d",&value,&weight);
      for(k=0;k<=w;k++){
	//cout<<j<<" "<<k<<endl;
	if(max_value[j-1][k]<0)
	  continue;
       	//cout<<j<<" "<<k<<endl;
	max_value[j][k]=max(max_value[j][k],max_value[j-1][k]);//j????????????????????\?????????
	
	//cout<<" "<<j<<" "<<k<<endl;
	int a,b;
	/*
	cout<<"debug"<<endl;
	rep(a,n+1){
	  rep(b,w+1)
	    printf(" %2d",max_value[a][b]);
	  cout<<endl;
	}
	*/
       
	if(k+weight<=w)
	  max_value[j][k+weight]=max(max_value[j][k+weight],max_value[j-1][k]+value);//??\??????
	/*
	cout<<"debug"<<endl;
	rep(a,n+1){
	  rep(b,w+1)
	    printf(" %2d",max_value[a][b]);
	  cout<<endl;
	}
	*/
      }
    }


    cout<<"Case "<<i<<":"<<endl;

    int max=0;
    int maxi=w+1;

    for(j=n;j>=0;j--){
      for(k=w;k>=0;k--)
	//	cout<<max_value[j][k]<<" ";
	if(max_value[j][k]>=max && maxi>k){
	  max=max_value[j][k];
	  maxi=k;
	  //	  cout<<"maxi"<<k<<endl;
	}
      //	cout<<endl;
    }
    cout<<max<<endl;
    cout<<maxi<<endl;
    i++;
  }
}

C++: #include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define fr first
#define sc second
using namespace std;

int w,n;
typedef pair<int,int> P;
P dp[1001][1001];
bool chg[1001][1001];
vector <P> dat;

P rec(int idx,int wi){
    P ans;
    if(chg[idx][wi]) return dp[idx][wi];
    if(idx == n){
        ans = P(0,wi);
    }
    else{
        if(wi - dat[idx].sc >= 0){
            P p = rec(idx+1,wi-dat[idx].sc);
            p.first += dat[idx].fr;
            ans = max(p,rec(idx+1,wi));
        }
        else ans = rec(idx+1,wi);
    }
    chg[idx][wi] = true;
    return dp[idx][wi] = ans;
}

int main(){
    while(cin >> w,w){
        int a = 0;
        memset(dp,-1,sizeof(dp));
        memset(chg,false,sizeof(chg));
        cin >> n;
        for(int i=0;i<n;i++){
            int t,m; scanf("%d,%d",&t,&m); dat.push_back(P(t,m));
        }
        P p = rec(0,w);
        cout << "Case " << ++a << ":\n" << p.fr << endl << w - p.sc << endl;
        dat.clear();
    }
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

struct Treasure
{

  int value;
  int weight;

  Treasure()
  {
    value = 0;
    weight = 0;
  }

  void operator()( Treasure t)
  {

    cout << t.value << "," << t.weight << endl;

  }

  Treasure& operator+=(const Treasure& t )
  {

    this->value += t.value;
    this->weight += t.weight;
    return *this;

  }

  Treasure operator+(const Treasure& t)
  {
    Treasure tmp;
    tmp.value = this->value + t.value;
    tmp.weight = this->weight + t.weight;
    return tmp;
  }

  Treasure operator-(const Treasure& t)
  {
    Treasure tmp;
    tmp.value = this->value - t.value;
    tmp.weight = this->weight - t.weight;
    return tmp;
  }

};

Treasure& max(Treasure& t1,Treasure& t2)
{

  if(t1.value == t2.value)
    {
      return (t1.weight < t2.weight) ? t1 : t2;
    }
  else
    {
      return (t1.value > t2.value) ? t1 : t2;
    }

}

int N,W;

Treasure memo[1000][1000];

Treasure tmp;

vector<Treasure> treasure(1000);

Treasure& Knapsack(int& currentWeight,int& currentCount)
{

  Treasure t1,t2,f;

  if(memo[currentWeight][currentCount].weight)
    {
      return memo[currentWeight][currentCount];
    }
  else if(N == currentCount)
    {
      return tmp;
    }
  else{

    t1 = Knapsack(currentWeight,currentCount + 1);

    if( W >= currentWeight + treasure[currentCount].weight)
      {
        t2 = Knapsack(currentWeight + treasure[currentCount].weight,currentCount + 1) + treasure[currentCount];
      }
    else
      {
        t2 = Knapsack(currentWeight,currentCount + 1);
      }

    memo[currentWeight][currentCount] = max(t1,t2);

    return max(t1,t2);

  }

}

int main()
{

  int caseNumber = 0;

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

     cin >> N;

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

     Treasure result = Knapsack(0,0);

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

     treasure.erase(treasure.begin(),treasure.end());

     cout << "Case " << ++caseNumber << ":" << endl;

     cout << result.value << endl << result.weight << endl;

   }

 return 0;

}

C++: #include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)

int caseId = 0;

void solve42(int W, int N) {
    int dp[1001] = {}; // dp[i]: maxvalue under weight i
    REP(i,N) {
        int a, b;
        char c;
        cin >> a >> c >> b;
        for(int j = W; j >= b; j--) {
            dp[j] = max(dp[j], dp[j-b] + a);
        }
    }
    int value = 0, weight = 0;
    int x = 0, y = 0;
    REP(i,W) if(x < dp[i]) x = dp[i], y = i;
    cout << "Case " << ++caseId << ":\n" << x << "\n" << y << "\n";
}

int main() {
    int W, N;
    while (cin >> W >> N, W) {
        solve42(W, N);
    }
    return 0;
}

C++: #include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <map>
#define INF 100000000
#define rep(i,a) for(int i=0;i<(a);i++)

using namespace std;
typedef long long ll;

int dp[1001][10001];    //dp[i][j]  i番目以前の物で、重さがj以下の時の価値
int W[1001],V[1001];

int w,n;

void solve(){
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<=w;j++){
            if(j-W[i]<0){
                dp[i][j]=dp[i+1][j];
            }
            else{
                dp[i][j]=max(dp[i+1][j],dp[i+1][j-W[i]]+V[i]);
            }
            
        }
    }
    
    cout<<dp[0][w]<<endl;
    for(int i=w;i>=1;i--){
        if(dp[0][i]!=dp[0][i-1]){
            cout<<i<<endl;
            break;
        }
    }
}

int main(){
    int count=1;
    while(1){
        memset(dp,0,sizeof(dp));
    
        cin>>w>>n;
        if(w==0)break;
        char a;
        rep(i,n)cin>>V[i]>>a>>W[i];
    
        cout<<"Case "<<count<<":"<<endl;
        count++;
        solve();
    }
    return 0;
}