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 <map>
#include <algorithm>
#include <cstdint>

typedef std::uint32_t WeightType;
typedef std::uint32_t ValueType;
typedef std::map<WeightType, ValueType> DPMap;

class LessSecond {
public:
	bool operator()(DPMap::value_type lhs, DPMap::value_type rhs) const
	{ return lhs.second < rhs.second; }
};

int main()
{
	std::uint32_t count = 0;
	WeightType W;
	for (std::cin >> W; W != 0; std::cin >> W) {
		DPMap dp_map;
		dp_map.insert(DPMap::value_type(0u, 0u));

		std::uint16_t n;
		std::cin >> n;

		for (std::uint32_t i = 0; i < n; ++i) {
			ValueType value;
			WeightType weight;
			(std::cin >> value).ignore() >> weight;

			for (auto it = dp_map.rbegin(); it != dp_map.rend(); ++it) {
				WeightType const new_weight = it->first + weight;
				ValueType const new_value = it->second + value;
				if (new_weight <= W) {
					auto insert_pos = dp_map.lower_bound(new_weight);
					if (insert_pos != end(dp_map) and
							not dp_map.key_comp()(new_weight, insert_pos->first)) {
						insert_pos->second = std::max(insert_pos->second, new_value);
					}
					else {
						dp_map.insert(insert_pos, DPMap::value_type(new_weight, new_value));
					}
				}
			}
		}

		auto max_pos = std::max_element(begin(dp_map), end(dp_map), LessSecond());
		std::cout << "Case " << ++count << ":\n"
				  << max_pos->second << "\n"
				  << max_pos->first << std::endl;
	}
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  int m;
  int co=0;
  while(cin>>m,m){
    co++;
    int n;
    char d;
    cin>>n;
    vector<int>w(n),v(n);
    vector<vector<int> >dp(n+1);
    rep(i,m+1)dp[0].pb(0);
    rep(i,n)cin>>v[i]>>d>>w[i];
    rep(i,n){
      //dp[i].pb(0);
      rep(j,m+1){
	if(w[i]>j)dp[i+1].pb(dp[i][j]);
	else dp[i+1].pb(max(dp[i][j],dp[i][j-w[i]]+v[i]));
      }
    }
    int maxi=0;
    rep(i,m)if(dp[n][i]==dp[n][m]){maxi=i;break;}

    cout<<"Case "<<co<<":"<<endl;
    cout<<dp[n][m]<<endl;
    cout<<maxi<<endl;
  }


}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int w,n;
int kati[1111],omo[1111];
int memo[1111][1111];
int solve(int ima,int omosa);
int main(){
  int cas=0;
  int anskati=0;
  int ansomo;
  while(1){
    for(int i=0;i<1111;i++){
      for(int j=0;j<1111;j++){
	memo[i][j]=0;
      }
    }
    
    cas++;
    cin>>w;
    if(w==0) break;
    cin>>n;
    for(int i=0;i<n;i++){
      scanf("%d,%d",&kati[i],&omo[i]);
    }
    cout<<"Case "<<cas<<':'<<endl;
    
    for(int i=1;i<=n;i++){
      for(int j=1;j<=w;j++){
	if(j<omo[i-1]){
	  memo[i][j]=memo[i-1][j];
	}else{
	  memo[i][j]=max(memo[i-1][j],memo[i-1][j-omo[i-1]]+kati[i-1]);
	}
      }
    }
    for(int i=0;i<=w;i++){
      if(memo[n][i]>anskati){
	anskati=memo[n][i];
	ansomo=i;
      }
    }
    cout<<anskati<<endl<<ansomo<<endl;
    
  }
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <list>
#include <numeric>
#include <utility>
#include <ctime>
#define INF 100000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#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 all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;

/*---------------------------------------------------*/

int W,N;
int v[1005],w[1005];
int dp[1005][1005];

void DEBUG(){
  rep(i,W+1)cout<<i<<": "<<dp[N][i]<<endl;
}

void init(){
  rep(i,1005){
    rep(j,1005){
      dp[i][j]=-INF;
    }
  }
}

void DP(){
  for(int i=0;i<1005;i++)dp[0][i]=0;
  
  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-w[i]]+v[i],dp[i][j]);
      else dp[i+1][j]=dp[i][j];
    }
  }
}

int main(){
  int cnt=1;
  while(cin>>W){
    init();
    if(W==0)break;
    cin>>N;
    rep(i,N)scanf("%d,%d",&v[i],&w[i]);
    
    DP();

    //DEBUG();
    int ans_value=0,ans_weight=0;
    rep(i,W+1){
      if(dp[N][i]>ans_value){
	ans_value=dp[N][i];
	ans_weight=i;
      }
    }
    cout<<"Case "<<cnt<<":"<<endl;
    cout<<ans_value<<endl;
    cout<<ans_weight<<endl;
    cnt++;
  }
  return 0;
}

C++: #include <iostream>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> P;

int main()
{
	int W,N,csn = 1;
	char ch;
	while(cin >> W,W){
		cin >> N;
		vector< P > takara(N + 1);
		vector< vector< int > > dp(N + 1, vector< int >(W + 1,0));
		for(int i = 1;i <= N;i++){
			cin >> takara[i].first >> ch >> takara[i].second;
		}
		for(int i = 1;i <= N;i++){
			for(int j = 1;j <= W;j++){
				if ((j - takara[i].second >= 0) && (dp[i - 1][j - takara[i].second] + takara[i].first > dp[i - 1][j])) {
					dp[i][j] = dp[i - 1][j - takara[i].second] + takara[i].first;
				}
				else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		int n = W;
		while (dp[N][n] == dp[N][W])
			n--;
		cout << "Case " << csn << ":" << endl;
		cout << dp[N][W] << endl;
		cout << n + 1 << endl;
		csn++;
	}
	return 0;
}

C++: //dp
#include<cstdio>
#include<iostream>
using namespace std;

int W,N,value[1000],weight[1000],cost;
int dp[1001][10000],data=0,w;
int main(){

  while(cin >>W){
    if(W==0)break;
    cin >>N;
    data++;
    for(int i=0;i<N;i++) scanf("%d,%d",&value[i],&weight[i]);
   
    for(int i=0;i<N;i++){ //どのお宝を選んでいるか
      for(int j=0;j<=W;j++){
	dp[i+1][j] = max (dp[i+1][j],dp[i][j]);
	if(j+weight[i]<=W)
	dp[i+1][j+weight[i]] = max(dp[i+1][j+weight[i]],dp[i][j]+value[i]);
      }
    }
    cost=dp[N][W];
    w=-1;
   
	for(int j=0;j<=W;j++){
	  if(dp[N][j] == cost){
	    w=j;
	    break;
	  }	  
	  //      cout <<weight[i]<<endl;
    }
      cout <<"Case "<<data<<":\n"<<cost<<endl<<w<<endl;
  }

  return 0;
}