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>
using namespace std;

int main(){
	int w, cntcase = 1;
	while (cin >> w, w){
		int n, dp[1000], treas_val, treas_w, ans_val = 0, ans_w = 0;
		cin >> n;
		for (int i = 0; i < w; i++) dp[i] = -1;
		dp[0] = 0;
		for (int i = 0; i < n; i++){
			scanf("%d,%d", &treas_val, &treas_w);
			for (int j = w - 1; j >= 0; j--){
				if (dp[j] != -1 && j + treas_w < w && dp[j + treas_w] < dp[j] + treas_val){
					dp[j + treas_w] = dp[j] + treas_val;
				}
			}
		}
		for (int i = 0; i < w; i++){
			if (ans_val < dp[i]){
				ans_val = dp[i];
				ans_w = i;
			}
		}
		printf("Case %d:\n%d\n%d\n", cntcase, ans_val, ans_w);
		cntcase++;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++ )
typedef pair<int,int> mypair;
int main(){
	int w,n;
	int casen = 1;
	while(1){
		cin>>w;
		if(w==0)break;
		cin>>n;
	vector<int> v(n),we(n);
	rep(i,n)scanf("%d,%d",&v[i],&we[i]);
	vector<vector<int> > dp(n+1,vector<int> ( w+1,0) );
	rep(i,n)rep(j,w+1){
	if(j<we[i])dp[i+1][j]=dp[i][j];
	else dp[i+1][j] = max(dp[i][j],dp[i][j-we[i]]+v[i]);
	}
	mypair ans = mypair(0,0);
	rep(i,w+1)ans = max(ans,mypair(dp[n][i],-i));
	cout<<"Case "<<casen<<":"<<endl;
	cout<<ans.first<<endl<<-ans.second<<endl;
		casen++;
	}


	return 0;
}

C++: #include <iostream>

using namespace std;

void rec(int i, const int weight, const int n, int v[], int w[], int *sum_w, int *sum_v)
{
  //?????????
  if (i+1 == n) {
    if (weight >= w[i] + *sum_w) {
      *sum_w += w[i];
      *sum_v += v[i];
    } 
    
  }
  //?????§?????????
  else {
    int tmpw, tmpv;
    tmpw = *sum_w;
    tmpv = *sum_v;
    
    int w1, v1, w2, v2;
    //?¢??????\??????
    if (weight >= w[i] + tmpw) {
      *sum_w += w[i];
      *sum_v += v[i];
      
      rec(i+1, weight, n, v, w, sum_w, sum_v);
      
      w1 =  *sum_w;
      v1 =  *sum_v;

    } else { v1 = 0; }
    
    *sum_w = tmpw;
    *sum_v = tmpv;
    
    //?¢??????\?????????
    rec(i+1, weight, n, v, w, sum_w, sum_v);
    
    if (weight >= *sum_w) {
      w2 = *sum_w;
      v2 = *sum_v;
    }

    if (v1 > v2) {
      *sum_w = w1;
      *sum_v = v1;
    } else {
      *sum_w = w2;
      *sum_v = v2;
    }
    
  }
  
}

void rec2(int i, const int weight, const int n, int v[], int w[], int *sum_w, int *sum_v, int **dp)
{
  if (dp[i][*sum_w] != -1) {
    
    *sum_v = dp[i][*sum_w];
  }
  else {
  if (i == n) {
    *sum_v = 0;
  }
  else {
    int tmpw, tmpv;
    tmpw = *sum_w;
    tmpv = *sum_v;
    
    int w1, v1, w2, v2;

    if (weight >= w[i] + tmpw) {
      *sum_w += w[i];
      
      rec2(1+i, weight, n, v, w, sum_w, sum_v,dp);

      w1 = *sum_w;
      v1 = *sum_v + v[i];
    } else { v1 = -1; w1 = -1; }
    *sum_w = tmpw;
    *sum_v = tmpv;

    rec2(1+i, weight, n, v, w, sum_w, sum_v, dp);

    w2 = *sum_w;
    v2 = *sum_v;

    if (v1 > v2) {
      *sum_w = w1;
      *sum_v = v1;
    } else {
      *sum_w = w2;
      *sum_v = v2;
    }
   
  }

  dp[i][*sum_w] = *sum_v;
  }
}

int main(void)
{
  int count = 1;
  while (true) {
    
    int weight, n;
    cin >> weight;
    if (weight == 0) break;
    cin >> n;
    int v[n], w[n];
    char c;
    for (int i = 0; i < n; i++) cin >> v[i] >> c >> w[i];
    //??\?????????

    int **dp;

    dp = (int **)malloc(sizeof(int*)*(n+1));
    for (int i = 0; i < n+1; i++)
      dp[i] = (int *)malloc(sizeof(int)*(weight+1));

    for (int i = 0; i < n+1; i++)
      for (int j = 0; j < weight+1; j++)
	dp[i][j] = -1;
    
    
    int huroshiki, value;
    int *sum_w, *sum_v;

    huroshiki = 0;
    value = 0;
    sum_w = &huroshiki; sum_v = &value;

    
    
    rec2(0, weight, n, v, w, sum_w, sum_v, dp);
    
    cout << "Case " << count << ":" << endl;
    cout << value << endl;
    cout << huroshiki << endl;
    
    count++;
  }

  return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int tr[1001][2],dp[1001][1001];
int main(){
  int w,n,c=1;
  while(cin >>w,w){
    cin >>n;
    for(int i=0; i<1001; i++) for(int j=0; j<1001; j++) dp[i][j] = 0;
    for(int i=1; i<=n; i++) scanf("%d,%d",&tr[i][0],&tr[i][1]);
    for(int i=1; i<=n; i++){
      for(int j=0; j<=w; j++){
	dp[i][j] = max(dp[i][j],dp[i-1][j]);
	if(j+tr[i][1]<=w) dp[i][j+tr[i][1]] = max(dp[i][j+tr[i][1]],dp[i-1][j]+tr[i][0]);
      }
    }
    int ans = 0,y;
    for(int i=0; i<=w; i++){
      if(ans < dp[n][i]){ans = dp[n][i];y = i;}
    }
    cout <<"Case "<<c<<":"<<endl<<ans<<endl<<y<<endl;
    c++;
  }
  return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<sstream>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const ll MOD=1000000007;
int n,w;
int t;
int main()
{
	t=1;
	while(cin>>w,w)
	{
		int dp[1001][1001]={0};
		cin>>n;
		vector<P> num(n);
		for(int i=0;i<n;i++)
		{
		 	char tt;
		 	int x,y;
		 	cin>>x>>tt>>y;
		 	num[i].first=x;
		 	num[i].second=y;
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<=w;j++)
			{
				if(num[i].second-j<=0)dp[i+1][j]=max(dp[i][j],dp[i][j-num[i].second]+num[i].first);
				else dp[i+1][j]=dp[i][j];
			}
		}
		cout<<"Case "<<t<<":"<<endl;;
		t++;
		int mmax=0;
		int ans;
		for(int i=w;i>=0;i--)
		{
			if(mmax<=dp[n][i])
			{
				mmax=dp[n][i];
				ans=i;
			}
		}
		cout<<mmax<<endl;
		cout<<ans<<endl;
	}
	return 0;
}

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

using namespace std;
int N;
int W;
vector<int> takaraW;
vector<int> takaraK;
vector<int> olddp;
vector<int> dp;

int main(){
    int kl = 1;
    while(true){
        takaraK.clear();
        takaraW.clear();
        dp.clear();
        cin >> W;
        if(W==0) return 0;
        cin >> N;
        takaraK.resize(N);
        takaraW.resize(N);
        dp.resize(W+1);
        for(int i=0;i<N;i++){
            char comma;
            cin >> takaraK[i] >> comma >>  takaraW[i];
        }
        for(int i=0;i<N;i++){
            olddp = dp;
            for(int j=0;j<W;j++){
                int neww = takaraW[i]+j;
                int newk = takaraK[i]+olddp[j];
                int oldk = olddp[neww];
                if(neww > W) continue;
                if(oldk < newk){
                    dp[neww] = newk;
                }
            }
        }
        int mw=W+2,mk=-1;
        for(int i=0;i<=W;i++){
            if(mk < dp[i]){
                mk = dp[i];mw = i;
            }
        }
        cout << "Case " << kl++ << ":" << endl;
        cout << mk << endl;
        cout << mw << endl;
    }
    return 0;
}