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>
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){
					if(dp[i-1][j]>=dp[i-1][j-w[i]]+v[i])
						dp[i][j]=dp[i-1][j];
					else
						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-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)
					dp[i][j]=-1;
			}
		}
	}
	int c=0;
	for(int j=0;j<t;j++){
		if(dp[n-1][j]>c)
			c=dp[n-1][j];
	}
	k++;
	for(int j=0;j<t;j++){
		if(c==dp[n-1][j]){
			cout<<"Case "<<k<<":"<<endl;
			cout<<c<<endl;
			cout<<j<<endl;
		}
	}
	}
	return 0;
}

C++: #include<iostream>

using namespace std;

class item
{
public:
	int value;
	int weight;
};

bool input(int *c, int *n, item it[1000])
{
	cin>>*c;
	if(*c==0)
	{
		return false;
	}
	cin>>*n;
	for(int i=0;i<*n;i++)
	{
		char t;
		cin>>it[i].value>>t>>it[i].weight;
	}
	return true;
}

item max(item a, item b)
{
	if(a.value>b.value)
	{
		return a;
	}
	else
	{
		return b;
	}
}

item add(item a, item b)
{
	a.value+=b.value;
	a.weight+=b.weight;
	return a;
}

item solve(int c, int n, item it[1000])
{
	if(c==0||n==0)
	{
		item ans;
		ans.value=0;
		ans.weight=0;
		return ans;
	}
	else if(c<it[n-1].weight)
	{
		return solve(c,n-1,it);
	}
	else
	{
		return max(solve(c,n-1,it),add(solve(c-it[n-1].weight,n-1,it),it[n-1]));
	}
}

int main(void)
{
	int c,n;
	item it[1000];
	for(int i=1;input(&c,&n,it);i++)
	{
		item ans=solve(c,n,it);
		cout<<"Case "<<i<<':'<<endl<<ans.value<<endl<<ans.weight<<endl;
	}
}

C++: #include <bits/stdc++.h>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const double eps=1e-9;
const int inf=1e9;
typedef pair<int,int> P;
struct Point
{
  double x,y;
  Point(){x=0;y=0;}
  Point(double d_x,double d_y){x=d_x,y=d_y;}
  double operator*(Point obj){return obj.x*x+obj.y*y;}
  double operator%(Point obj){return obj.y*x-obj.x*y;}
  Point operator*(double b){Point tmp;tmp.x=x*b;tmp.y=y*b;return tmp;}
  Point operator/(double b){Point tmp;tmp.x=x/b;tmp.y=y/b;return tmp;}
  Point operator+(Point obj){Point tmp;tmp.x=x+obj.x;tmp.y=y+obj.y;return tmp;}
  Point operator-(){Point tmp;tmp.x=-x;tmp.y=-y;return tmp;}
  Point operator-(Point obj){Point tmp;tmp.x=x-obj.x;tmp.y=y-obj.y;return tmp;}
  Point operator-=(Point obj){x-=obj.x;y-=obj.y;return *this;}
  Point operator+=(Point obj){x+=obj.x;y+=obj.y;return *this;}
  Point operator/=(double b){x=x/b;y=y/b;return *this;}
  Point operator*=(double b){x=x*b;y=y*b;return *this;}
  double size(){return hypot(x,y);}
  Point unit(){return Point(x/size(),y/size());}
  Point normal(){return Point(y,-x);}
  double atan(){return atan2(y,x);}
};

bool operator<(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
bool operator>(Point a,Point b){return b<a;}
bool operator<=(Point a,Point b){return !(b<a);}
bool operator>=(Point a,Point b){return !(a<b);}
bool operator==(Point a,Point b){return (a-b).size()<eps;}
bool operator!=(Point a,Point b){return !(a==b);}

bool equal(double a,double b){return abs(a-b)<eps;}
double cross(Point a,Point b){return a%b;}
double dot(Point a,Point b){return a*b;}

int ccw(Point a,Point b,Point c)
{
  b=b-a;
  c=c-a;
  if(b%c>0) return +1;
  else if(b%c<0)return -1;
  else if(b*c<0) return +2;
  else if(b.size()<c.size()) return -2;
  else return 0;
}

int w,h;
vector<string> board;
vector<vector<string> > memo;
int dx[]={1,0};
int dy[]={0,1};

inline bool outrange(int x,int y)
{
  return (x<0 || x>=w || y<0 || y>=h);
}

string cmp(string a,string b)
{
  if(a.size()>b.size()) return a;
  if(b.size()>a.size()) return b;
  return max(a,b);
}

string dfs(int x,int y)
{
  if(outrange(x,y)) return "";
  if(!isdigit(board[y][x])) return "";
  if(memo[y][x]!="") return memo[y][x];
  
  string res="";
  for(int d=0;d<2;d++)
    {
      res=cmp(res,board[y][x]+dfs(x+dx[d],y+dy[d]));
    }
  memo[y][x]=res;
  return res;
}

int main(int argc,char const* argv[])
{
  int W,N;
  int v[1005];
  int w[1005];
  int dataset=0;
  int dp[1005][1005];
  while(1)
    {
      dataset++;
      memset(w,0,sizeof(w));
      memset(v,0,sizeof(v));
      memset(dp,0,sizeof(dp));
      cin >> W;
      if(!W) break;
      cin >> N;
      for(int i=1;i<=N;i++)
	{
	  bool comma=false;
	  string s;
	  cin >> s;
	  string value="";
	  string weight="";
	  for(int j=0;j<int(s.size());j++)
	    {
	      if(!comma && s[j]!=',')
		{
		  value+=s[j];
		}
	      else if(s[j]==',')
		{
		  comma=true;
		  continue;
		}
	      else if(s[j]!=',' && comma)
		{
		  weight+=s[j];
		}
	    }
	  v[i]=stoi(value);
	  w[i]=stoi(weight);
	}
      for(int i=1;i<=N;i++)
	{
	  for(int j=0;j<=W;j++)
	    {
	      if(j-w[i]>=0)
		{
		  dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
		}
	      dp[i][j]=max(dp[i][j],dp[i-1][j]);
	    }
	}
      int ansv=-1;
      int answ=-1;
      for(int i=0;i<=W;i++)
	{
	  if(dp[N][i]>ansv)
	    {
	      ansv=dp[N][i];
	      answ=i;
	    }
	}
      cout << "Case " << dataset << ':' << endl;
      cout << ansv <<endl;
      cout << answ << endl;
    }
  return 0;
}