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<sstream>
#include<vector>
#include<map>
#define pb(a) push_back(a)
using namespace std;
typedef pair<int,int> P;
int main(){
  int c=0;
  int w,n,i,j,k;;
  while(cin >> w,w){
    c++;
    cout << "Case "<<c<<":"<<endl;
    cin >> n;
    string s;
    vector<P> v;
    P p,ans;
    for(k=0;k<n;k++){
      cin >> s;
      for(i=0;i<s.size();i++) if(s[i]==',') s[i]=' ';
      stringstream ss(s);
      ss>>p.first >>p.second;
      v.pb(p);
    }
    int dp[1005][1005]={{}};
    int inf = 1 << 20;
    fill(dp[0],dp[1004],-inf);
    dp[0][0]=0;
    for(i=0;i<n;i++){
      //cout << v[i].first << ":" << v[i].second << endl;
      for(j=0;j+v[i].second<=w;j++){
	if(dp[i][j]==-inf) continue;
	dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
	dp[i+1][j+v[i].second]=max(dp[i+1][j],dp[i][j]+v[i].first);
	//cout << dp[i+1][j]<<endl;
      }
    }
    ans.first=0;ans.second=0;
    for(i=0;i<=w;i++){
      //cout << i << ":" << dp[1][i] << endl;
      if(dp[n][i]>ans.first){
	ans.first=dp[n][i];
	ans.second=i;
      }
    }
    cout << ans.first << endl << ans.second << endl;
  }
  return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <cstdio>

#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;

int main(){
	int c = 1;
	int w;
	while(cin >> w && w){
		int n;
		int tr[1024][2];
		// 価値を最大に
		// 重さ合計 価値
		int dp[1024];
		
		cin >> n;
		rep(i, n){
			scanf("%d, %d", &tr[i][0], &tr[i][1]);
		}

		rep(i, w + 1){
			dp[i] = 0;
		}
		
		rep(i, n){
			for(int j = w; j >= 0; j--){
				if(dp[j] != -1){
					int we = j + tr[i][1];
					if(we <= w){
						dp[we] = max(dp[we], dp[j] + tr[i][0]);
					}
				}
			}
		}
	
		int mv,mw;
		mv = 0; mw = 0;
		rep(i, w){
				if(dp[i] > mv){
					mv = dp[i];
					mw = i;
				}
		}

		cout << "Case " << c << ':' << endl;
		cout << mv << endl;
		cout << mw << endl;

		c++;
	}
	return 0;
}

C++: #include<cstdio>
#include<iostream>

const int MAX_ITEMS = 1001;

using namespace std;

class CItem{
public:
	CItem(){
		val = 0;
		wgh = 0;
	}
	int val;
	int wgh;
	bool operator<(const CItem &a) const {
		if( val < a.val ){
			return true;
		}else if( val == a.val ){
			if( wgh > a.wgh ){
				return true;
			}
		}
		return false;
	}
	CItem operator+(const CItem &a){
		CItem ret;
		ret.val = val + a.val;
		ret.wgh = wgh + a.wgh;
		return ret;
	}
};

void compute( CItem *Items, CItem **D, int H, int W ){
	for(int i = 1; i < H; i++){
		for(int j = 1; j < W; j++){
			CItem zeroItem;
			CItem m1 = D[i - 1][j];
			CItem m2 = j - Items[i].wgh < 0 ? zeroItem : D[i - 1][j - Items[i].wgh] + Items[i];
			D[i][j] = max( m1, m2 );
		}
	}
}

int main(void){
	int datasetIndex = 0;
	while( true ){
		CItem **D;
		CItem Items[MAX_ITEMS];
		int W, N;

		datasetIndex++;

		scanf("%d",&W);if( W == 0 )break;
		scanf("%d",&N);N++;W++;

		for(int i = 1; i < N; i++){
			scanf("%d,%d", &Items[i].val, &Items[i].wgh);
		}

		D = new CItem*[N];
		for(int i = 0; i < N; i++){
			D[i] = new CItem[W];
		}

		compute( Items, D, N, W );

		printf("Case %d:\n%d\n%d\n", datasetIndex, D[N-1][W-1].val, D[N-1][W-1].wgh);

		for(int i = 0; i < N; i++){
			delete[] D[i];
		}
		delete[] D;
	}
	return 0;
}

C++: #include<stdio.h>
#include<string.h>
#include<math.h>
int a,s,d[1001],f[1001],g[1001][1001],h,i,j,z,x;
int main(void)
{
	x=1;
	while(1){
		scanf("%d",&a);
		if(a==0)	break;
		scanf("%d",&s);
		for(i=0;i<s;i++)
			scanf("%d,%d",&d[i],&f[i]);
		for(i=0;i<=s;i++){
			for(j=0;j<=a;j++)
				g[i][j]=-1;
		}
		g[0][0]=0;
		for(i=0;i<s;i++){
			for(j=0;j<=a;j++){
				if(g[i][j]!=-1){
					if(g[i][j]>g[i+1][j])
						g[i+1][j]=g[i][j];
					if(j+f[i]<=a){
						if(g[i][j]+d[i]>g[i+1][j+f[i]])
							g[i+1][j+f[i]]=g[i][j]+d[i];
					}
				}
			}
		}
		h=0;
		z=0;
		for(i=0;i<=a;i++){
			if(h<g[s][i]){
				h=g[s][i];
				z=i;
			}
		}
		printf("Case %d:\n",x);
		printf("%d\n%d\n",h,z);
		x++;
	}
	return 0;
}

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

int main(){
    int a = 0;
    while(cin >> w,w){
        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.resize(0);
    }
}

C++: #include<stdio.h>
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int i,j,l;
int w;
int n;
int a;
int kati,omosa;
int casecnt=0;
int maxkati,maxomosa;
long long int dp[5000][1000];//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%c%d",&kati,&a,&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%c%d",&kati,&a,&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){
					dp[i][j+omosa]=dp[i-1][j]+kati;
					for(l=i;l<=n;l++){
						if(dp[i-1][j+omosa]>dp[l+1][j+omosa]);
						else {
							dp[l][j+omosa]=dp[i][j+omosa];
						}
					}
				}
			}
			for(j=i;j<=w;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("%d ",dp[i][j]);
			}
			printf("\n");
		}*/
		maxomosa=0;
		maxkati=0;
		for(j=0;j<=w;j++){
			if(maxkati<dp[n][j]){
				maxkati=dp[n][j];
				maxomosa=j;
			}
		}
		casecnt++;
		printf("case %d:\n",casecnt);
		printf("%d\n",maxkati);
		printf("%d\n",maxomosa);
		scanf("%d",&w);
	}
	return 0;
}