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 <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 treasure_type{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 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] = treasure_type{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), treasure_type{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(treasure_type{vi, wi});
    }

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

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
  int n;
  int w;
  int k=1;
  while(cin >> w >> n, w) {
    int p[n], a[w];
    REP(i, n) {
      scanf("%d,%d", &p[i], &a[i]);
    }
    int dp[n+1][w+1];           // dp[i][j]:iツ氾板姪堋づ慊づづ個陛ウツづ、ツ重ツつウツづ個堕債和ツつェjツ暗按可コツづ個づつォツづ個催妥・
    memset(dp, 0, sizeof(dp));
    REP(i, n) {
      REP(j, w+1) {
        if (j<a[i])
          dp[i+1][j] = dp[i][j];
        else
          dp[i+1][j] = dp[i][j-a[i]] + p[i];
      }
    }
    printf("Case %d:\n", k++);
    cout << dp[n][w] << endl;
    cout << lower_bound(dp[n], dp[n]+w+1, dp[n][w])-dp[n] << endl;
  }
}

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

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

int rec(int i, int j){

  //テ」ツつづ」ツ??」ツつ?」ツ?」テ」ツ??
  if(dp[i][j] >= 0){
    return dp[i][j];
  }
  int res;

  if(i == N){ // テ」ツつづ」ツ??・ツ督?ァツ可ゥテ」ツ?ッテァツ?。テ」ツ??
    res = 0;

  }else if(j < w[i]){ // テ」ツ?禿」ツ?ョテ・ツ督?ァツ可ゥテ」ツ?ッテ・ツ?・テ」ツつ嘉」ツ?ェテ」ツ??
    res = rec(i + 1,j);
 
  }else{ // テ・ツ督?ァツ可ゥテ」ツつ津・ツ環?」ツ?暗」ツつ凝」ツ?禿」ツ?ィテ」ツ?古・ツ?コテヲツ敖・テ」ツつ凝」ツ?ィテ」ツ??
        res = max(rec(i+1,j), rec(i+1,j-w[i]) + v[i]);
    /* 
   int tmp1,tmp2;
    tmp1 = rec(i+1,j);
    tmp2 = rec(i+1,j-w[i]) + v[i];
    if(tmp1 < tmp2){
      res = tmp2;
    }else{
      res = tmp1;
    }
    */
  }
  return dp[i][j] = res;
}


int main(){

  int num = 1;

  while(1){
    cin >> W;
    if(W == 0) break;
    cin >> N;
    //テ・ツ按敕ヲツ慊淌・ツ個?
    /*
    for(int i = 0; i < 1001; i++){
      w[i] = v[i] = -1;
      for(int j = 0; j < 1001; j++)
	dp[i][j] = -1; 
    }
    */
    memset(dp,-1,sizeof(dp));
    memset(w,-1,sizeof(w));
    memset(v,-1,sizeof(v));


    //テ・ツ?・テ・ツ環?
    char tmp;
    for(int i = 0; i < N; i++) cin >> v[i] >> tmp >> w[i];

    int ans = rec(0,W);

    // dpテゥツ?催・ツ按療」ツつ津・ツ?ィテ」ツ?ヲテ・ツ淞凝」ツつ?」ツつ?
    for(int i = 0; i < N; i++){
      for(int j = 0; j <= W; j++){
	if(dp[i][j] == -1)
	  rec(i,j);
      }
    }   
  
    cout << "Case "<< num  << ":"<< endl;
    num++;
    cout << ans << endl; 
    int j;
    for( j = 0; dp[0][j] != ans ; j++){}
    cout << j << endl;
    
  }
  return 0;
}

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

int main()
{
  int W,N,v,w,i,j;
  int cnt=0,maxv,maxw;
  vector< vector<int> > dp;
  while(cin>>W>>N,W){
    vector< vector<int> > dp(N+2,vector<int>(W+1));
    for(i=1;i<=N;i++){
      scanf("%d,%d",&v,&w);
      for(j=0;j<=W;j++){
	if(j>=w && dp[i][j] < dp[i-1][j-w]+v)dp[i][j]=dp[i-1][j-w]+v;
	else dp[i][j]=dp[i-1][j];
      }
    }
    maxv=maxw=0;
    for(j=0;j<=W;j++){
      if(maxv<dp[N][j]){maxv=dp[N][j];maxw=j;}
    }
    printf("Case %d:\n%d\n%d\n",++cnt,maxv,maxw);
  }
}

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

using namespace std;

int main(){

	int W;
	int n;

	int v[1001];
	int w[1001];

	int dp[1001][1001];

	int cs=0;
	while(cin>>W&&W!=0){
		cin>>n;
		for(int i = 0; i < n; i++){
			char cm;
			cin>>v[i]>>cm>>w[i];
		}

		for(int i = 0; i < n; i++){
			for(int j = 0; j <= 1000; j++){
				if(i==0){
					if(j==w[0]){
						dp[i][j]=v[i];
					}
					else{
						dp[i][j]=0;
					}
				}
				else{
					if(j-w[i]>=0){
						dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
					}
					else{
						dp[i][j]=max(dp[i][j],dp[i-1][j]);
					}
				}
			}
		}
		int idx=0;
		int maxNum=-1;
		for(int i = 0; i <= W; i++){
			if(maxNum<dp[n-1][i]){
				maxNum=dp[n-1][i];
				idx=i;
			}
		}
		cout<< "Case " << cs+1 << ':' << endl;
		cout<<maxNum<<endl;
		cout<<idx<<endl;

		cs++;
	}

	return 0;
}

C++: #include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int w[1000],v[1000];
int memo[1001][1001];
int dfs(int pos,int win){
    if(memo[pos][win]!=-1)return memo[pos][win];
    int res;
    if(pos<1)res=0;
    else if(win-w[pos-1]<0)res=dfs(pos-1,win);
    else res=max(dfs(pos-1,win),dfs(pos-1,win-w[pos-1])+v[pos-1]);
    return memo[pos][win]=res;
}
int main(){
    int W;
    for(int cnt=0;scanf("%d",&W),W;cnt++){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%d,%d",v+i,w+i);
        fill_n(*memo,1001*1001,-1);
        int ans=dfs(n,W);
        printf("Case %d:\n",cnt+1);
        for(int i=W-1;i>=0;i--){
            if(ans==dfs(n,i))continue;
            printf("%d\n%d\n",ans,i+1);
            break;
        }

    }
    return 0;
}