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<algorithm>
#include<map>
using namespace std;
typedef pair<int,int> P;

int main(){
	int W,N,cou=0;
	int tr[1001],we[1001];
	while(cin >> W , W){
		cou++;
		cin >> N;
		for(int i=1;i<=N;i++){
			scanf("%d,%d",&tr[i],&we[i]);
		}

		P dp[100][1001];
		for(int i=0;i<=N;i++){
			for(int j=0;j<=N;j++){
				dp[i][j] = P(0,0);
			}
		}
		dp[0][0] = P(0,0);
		for(int i=1;i<=N;i++){
			dp[i][0] = P(0,0);
			for(int j=0;j<i;j++){
				if(dp[i-1][j].second+we[i] <= W){
					P p;
					p = P(dp[i-1][j].first+tr[i],dp[i-1][j].second+we[i]);
					if(p.first == dp[i-1][j+1].first){
						if(p.second < dp[i-1][j+1].second) dp[i][j+1] = p;
						else dp[i][j+1] = dp[i-1][j+1];
					}
					else if(p.first > dp[i-1][j+1].first){
						dp[i][j+1] = p;
					}
				}
			}
		}

		cout << "Case " << cou << ":" << endl;
		cout << dp[N][N].first << endl;
		cout << dp[N][N].second << endl;

	}
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
//#include <stack>
//#include <queue>
//#include <map>
#include <cmath>
//#include <string>
//#include <sstream>
#include <iomanip>
//#include <complex>
#include <stdio.h>
//小数制度 	cout << fixed << setprecision(5) << tmp << endl;
using namespace std;

#define ll long long
#define vvi vector< vector<int> >
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int dp[1010][1010];
int v[1010];
int w[1010];
int main(){
  int wei,n;
  int cnt = 1;
  while(cin >> wei,wei){
    cin >> n;
    REP(i,1010) REP(j,1010) dp[i][j] = 0;
    w[0]=0;v[0]=0;
    for(int i=1;i<n+1;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<wei;j++){
        if(j-w[i]<0) dp[i+1][j] = dp[i][j];
        else  dp[i+1][j]=max(dp[i][j+1],dp[i+1][j-w[i-1]]+v[i-1]);
      }
    }
    /*for(int i=0;i<n+1;i++){
      for(int j=0;j<wei+1;j++){
        cout << dp[i][j] << " ";//l<<endl;
      }
      cout << endl;
    }*/
    int maxv=0;
    int ans=-1;
    for(int i=0;i<wei+1;i++){
      if(maxv < dp[n][i]){
        maxv = dp[n][i];
        ans = i;
      }
    }
    cout << "Case " << cnt << ":" <<endl;
    cout << maxv << endl << ans << endl;
    cnt++;
  }
}

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

#define N 1000
#define W 1000
#define INF 10001

#define max(a,b) (a>b?a:b)

int main() {
	static int dp[N+1][W+1];
	int tw[N+1], tv[N+1];
	int w, n, mv, mw, c=0; char dummy;

	while(1) {
		cin >> w;
		if(!w) break;
		c++; mw = INF; mv = 0;
		for(int i=0; i<N+1; ++i) {
			for(int j=0; j<N+1; ++j) {
				dp[i][j] = 0;
			}
		}
		cin >> n;
		for(int i=1; i<=n; ++i) cin >> tv[i] >> dummy >> tw[i];
		for(int i=1; i<=n; ++i) {
			for(int j=0; j<=w; ++j) {
				if(j-tw[i]>=0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-tw[i]]+tv[i]);
				else dp[i][j] = dp[i-1][j];
			}
		}
		for(int i=0; i<=w; ++i) {
			if(mv<dp[n][i]) {
				mw = i; mv = dp[n][i];
			}
		}
		cout << "Case " << c << ":" << endl;
		cout << mv << "\n" << mw << endl;
	}
	return 0;
}

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

int main(){
	int n,W;
	int v[1000],w[1000];
	for(int cnt = 0;;cnt++){
		cin >> W >> n;
		if(!W) break;
		int dp[1001][1001] = {},ma = 0,mi = 1e+9;
		for(int i = 0;i < n;i++){
			scanf("%d,%d",&v[i],&w[i]);
		}
		dp[0][0] = 0;
		for(int i = 1;i <= n;i++){
			for(int j = 0;j <= W;j++){
				if(j - w[i - 1] >= 0) dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i - 1]] + v[i - 1]);
				else dp[i][j] = dp[i - 1][j];
				if(ma < dp[i][j]){
					ma = dp[i][j];
					mi = j;
				}else if(ma == dp[i][j]) mi = min(mi,j);
			}
		}
		printf("Case %d:\n%d\n%d\n",cnt,ma,mi);
	}
	
	return 0;
}

C++: #include <cstdio>
#include <algorithm>
using namespace std;

int W, N;
int v[1000], w[1000], dp[1000+1][1000+1];

int main()
{
  int cnt = 1;
  while (~scanf("%d", &W)) {
    if (W == 0)
      break;

    for (int i = 0; i < 1001; ++i) {
      for (int j = 0; j < 1001; ++j)
	dp[i][j] = 0;
    }

    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
      scanf("%d,%d", &v[i], &w[i]);

    int maxV = -1, minW = 1 << 30;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < W+1; ++j) {
	if (j < w[i])
	  dp[i+1][j] = dp[i][j];
	else
	  dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i]);
	if (maxV < dp[i+1][j]) {
	  maxV = dp[i+1][j];
	  minW = j;
	} else if (maxV == dp[i+1][j]) {
	  minW = min(minW, j);
	}
      }
    }

    printf("Case %d:\n", cnt++);
    printf("%d\n%d\n", maxV, minW);
  }
  return 0;
}

C++: #include <algorithm>
#include <array>
#include <iostream>
#include <tuple>
#include <vector>

using treasure_type = std::tuple<int, int>;

treasure_type maximum(const treasure_type& a, const treasure_type& b) {
  if (std::get<0>(a) == std::get<0>(b)) {
    return {std::get<0>(a), std::min(std::get<1>(a), std::get<1>(b))};
  } else if (std::get<0>(a) > std::get<0>(b)) {
    return a;
  } else {
    return b;
  }
}

treasure_type maximum(const treasure_type& a, const treasure_type& b, const treasure_type& c) {
  return maximum(a, maximum(b, c));
}

treasure_type solve(int wmax, const std::vector<treasure_type>& ts) {
  std::array<std::vector<treasure_type>, 2> dp{};
  dp[0].resize(wmax + 1);
  dp[1].resize(wmax + 1);
  for (auto i = 0u; i <= wmax; ++i) {
    dp[0][i] = {0, 0};
  }

  for (auto i = 0u; i < ts.size(); ++i) {
    const auto& ti  = ts.at(i);
    const auto& dpp = dp.at(i % 2);
    auto& dpn       = dp.at((i + 1) % 2);
    for (auto j = 0u; j <= wmax; ++j) {
      if (j >= std::get<1>(ti)) {
        const auto& dppi2 = dpp[j - std::get<1>(ti)];

        dpn[j] = maximum(dpp.at(j), {std::get<0>(ti) + std::get<0>(dppi2),
                                     std::get<1>(ti) + std::get<1>(dppi2)});
      } else {
        dpn[j] = dpp.at(j);
      }
    }
  }

  return dp.at(ts.size() % 2).at(wmax);
}

auto main() -> int {
  for (int c = 1;; ++c) {
    int w;
    std::cin >> w;
    if (w == 0) break;

    int n;
    std::cin >> n;
    std::vector<treasure_type> ts{};
    for (int i = 0; i < n; ++i) {
      int vi, wi;
      std::scanf("%d,%d", &vi, &wi);
      ts.push_back({vi, wi});
    }

    const auto ans = solve(w, ts);
    std::cout << "Case " << c << ":\n"
              << std::get<0>(ans) << "\n"
              << std::get<1>(ans) << std::endl;
  }
}