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;
    }
  */
  if(memo[correntWeight][kind].flag) return memo[correntWeight][kind].record;
  else if(kind == treasurea.size() || correntWeight == 0)
    {
      Treasurea temp;
      temp.weight = W - correntWeight;
      temp.value = correntValue;
      return temp;
    }

  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<stdio.h>
int i,j,l;
int w;
int n;
int kati,omosa;
long long int maxkati,maxomosa,casecnt=0;
long long int dp[1005][1005];//dp[お宝の総数][お宝の重さ]
int main(void){
	scanf("%d",&w);
	while(w!=0){
		for(i=0;i<=1000;i++){
			for(j=0;j<=1000;j++){
				dp[i][j]=0;
			}
		}
		scanf("%d",&n);
		scanf("%d,%d",&kati,&omosa);
		dp[0][omosa]=kati;
		for(j=1;j<=n;j++){
			dp[j][omosa]=dp[0][omosa];
		}
		for(i=1;i<n;i++){
			scanf("%d,%d",&kati,&omosa);
			for(j=i;j<=n;j++){
				if(dp[j][omosa]<kati){
					dp[j][omosa]=kati;
				}
			}
			for(j=1;j<=w;j++){
				if(dp[i-1][j]>0){
					if(dp[i][j+omosa]<dp[i-1][j]+kati){	
						dp[i][j+omosa]=dp[i-1][j]+kati;
						for(l=i;l<=n;l++){
							dp[l][j+omosa]=dp[i][j+omosa];
						}
					}
				}
			}
			for(j=i;j<=n;j++){
				if(dp[i][j+omosa]>dp[j+1][j+omosa]){
					dp[j+1][j+omosa]=dp[i][j+omosa];
				}
			}
		}
		/*for(i=0;i<=n;i++){
			for(j=1;j<=w;j++){
				printf("%lld ",dp[i][j]);
			}
			printf("\n");
		}*/
		maxomosa=0;
		maxkati=0;
		for(j=0;j<=w;j++){
			if(maxkati==dp[n][j]);
			else if(maxkati<dp[n][j] ){
				maxkati=dp[n][j];
				maxomosa=j;
			}
		}
		casecnt++;
		printf("case %lld:\n",casecnt);
		printf("%lld\n",maxkati);
		printf("%lld\n",maxomosa);
		scanf("%d",&w);
	}
	return 0;
}

C++: #include<iostream>
#include<string>
int dp[1000][1000];
using namespace std;
int main(){
	int t,n;
	int w[2000],v[2000];
	int k=0;
	char z;
	while(true){
	cin>>t;
	if(t==0)
		break;
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<t;j++){
			dp[i][j]=-1;
		}
	}
	for(int i=0;i<n;i++){
		cin>>v[i]>>z>>w[i];
		dp[i][0]=0;
	}
	dp[0][w[0]]=v[0];
	for(int i=1;i<n;i++){
		for(int j=1;j<=t;j++){
			if(j-w[i]<0){
				if(dp[i-1][j]==-1)
					dp[i][j]=-1;
				if(dp[i-1][j]!=-1)
					dp[i][j]=dp[i-1][j];
			}
			if(j-w[i]>=0){
				if(dp[i-1][j]==-1&&dp[i-1][j-w[i]]==-1)
					dp[i][j]=-1;
				if(dp[i-1][j]==-1&&dp[i-1][j-w[i]]!=-1)
					dp[i][j]=dp[i-1][j-w[i]]+v[i];
				if(dp[i-1][j]!=-1&&dp[i-1][j-w[i]]==-1)
					dp[i][j]=dp[i-1][j];
				if(dp[i-1][j]!=-1&&dp[i-1][j-w[i]]!=-1){
					if(dp[i-1][j]>=dp[i-1][j-w[i]]+v[i])
						dp[i][j]=dp[i-1][j];
					if(dp[i-1][j]<dp[i-1][j-w[i]]+v[i])
						dp[i][j]=dp[i-1][j-w[i]]+v[i];
				}
			}
		}
	}
	int c=0;
	for(int j=0;j<=t;j++){
		if(dp[n-1][j]>c)
			c=dp[n-1][j];
	}
	k++;
	bool g=false;
	for(int j=0;j<=t;j++){
		if(c==dp[n-1][j]&&g==false){
			cout<<"Case "<<k<<":"<<endl;
			cout<<c<<endl;
			cout<<j<<endl;
			g=true;
		}
	}
	}
	return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <numeric>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<((x))<<endl
#define fi first
#define se second

#define INF 2147483600
#define long long long

int main(){
  int tc=1;
  int W;
  while(cin>>W, W){
    int n;
    cin>>n;
    vector<int> v(n), w(n);
    rep(i,n) scanf("%d,%d", &v[i], &w[i]);

    vector<int> dp(W+1, -INF);
    dp[0]=0;
    rep(i,n){
      for(int j=W; j-w[i]>=0; j--) if(j-w[i]>=0){
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
      }
    }
    int mw=0, mv=0;
    rep(i,W+1) if(dp[i]>mv){mv=dp[i], mw=i;}
    printf("Case %d:\n", tc); tc++;
    printf("%d\n%d\n", mv, mw);
  }

  return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include <utility>

using namespace std;


int main(){
	int dp[1000];
	
	int W,N;
	int v[1000],w[1000];
	
	int count=0;
	
	while(cin>>W,W){
		cin>>N;
		count++;
		for(int i=0;i<N;i++){
			scanf("%d,%d",&v[i],&w[i]);
		}
		
		for(int j=0;j<W;j++){
			if(j<w[0]){
				dp[j]=0;
			}else{
				dp[j]=v[0];
			}
		}
		
		for(int i=1;i<N;i++){
			for(int j=0;j<W;j++){
				if(j<w[i]){
					dp[j]=dp[j];
				}else{
					dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
				}
			}
		}
		
		cout<<"Case "<<count<<":"<<endl;
		cout<<dp[W-1]<<endl;
		int k;
		for(k=W;dp[k-2]==dp[k-1];k--);
		cout<<k<<endl;
	}
	
	
	
	
	return 0;
	
}