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

int dp[1005];

int main() {
    int n,w,t=1;
    while(scanf("%d", &w), w) {
        memset(dp, -1, sizeof(dp));
        scanf("%d", &n);
        dp[0] = 0;

        int v,x;
        for(int i=0; i<n; ++i) {
            scanf("%d,%d", &v,&x);
            for(int j=w; j>=0; --j) {
                if(dp[j] == -1 || j+x >= w) continue;
                dp[j+x] = max(dp[j+x],dp[j]+v);
            }
        }

        int ans = 0,ai = 0;
        for(int j=0; j<=w; ++j) {
            if(ans > dp[j]) ai = j;
            ans = max(ans, dp[j]);
        }
        printf("Case %d:\n%d\n%d\n", t++, ans, ai+1);
    }
}

C++: #include <iostream>
#include <map>
#include <stdio.h>
int main(){
  using std::cin;
  using std::cout;
  using std::endl;
  using std::map;
  int weight,n,w,v,s,c=1;
  map<int,int> m;
  while(cin>>weight){
    if(!weight)return 0;
    cin>>n;
    map<int,int>::iterator it;
    for(;n;n--){
      scanf("%d,%d",&v,&w);
      if(m.empty()){m[w]=v;continue;}
      it = m.begin();
      while(it!=m.end()){
	s=(*it).second+v;
	if((*it).first+w>=weight)break;
	if(m[(*it).first+w]<s)m[(*it).first+w]=(*it).second+v;
	it++;
      }
      m[w]=v;
    }
    it=m.end();
    it--;
    cout<<"Case "<<c++<<":"<<endl<<(*it).second<<endl<<(*it).first<<endl;
    m.clear();
  }
}

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

using namespace std;

const int W = 1001;
const int N = 1001; 

int table[W][N];

void solve(int n,int lim, vector<int> price, vector<int> weight){
  int maxi_p = 0,maxi_w = 0;
  for(int i = 0;i < W;i++){
    for(int j = 0;j < N;j++){
      table[i][j] = 0;
    }
  }
  
  /*
  for(int i = 0;i < n;i++){
    table[weight[i]][i] = price[i]; 
  }
  */
  table[weight[0]][0]=price[0];

  
  for(int i = 0;i <=lim;i++){
    for(int j = 1;j < n;j++){
      table[i][j] = table[i][j-1]; 
      if(i - weight[j] < 0)continue;
      table[i][j] =max(table[i - weight[j]][j-1]+price[j],table[i][j-1]);
    } 
  }

  for(int i = 0;i <= lim;i++){
    if(maxi_p < table[i][n-1]){
      maxi_p = table[i][n-1];
      maxi_w = i;
    }

    
  }
  cout << maxi_p << endl; 
  cout << maxi_w << endl;
}  

int main(){
  int count = 1;
  int lim;
  int n;
  int price,weight;  
  while(cin >> lim >> n &&lim){

    vector<int> a,b;
    int tmp;
    char damy;
    cout << "Case "<< count <<":"<<endl;
    for(int i = 0;i < n;i++){
      cin >> price >> damy >> weight;
      a.push_back(price);
      b.push_back(weight);
    }
    
    solve(n,lim,a,b);
    count++;
  }
  return 0;
}

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

int main() {
  int t=1,w;
  while(cin >> w && w!=0) {
    int n;
    cin >> n;
    int a[n][2];
    for(int i=0; i<n; i++) {
      scanf("%d%*c%d",&a[i][0],&a[i][1]);
    }
    int dp[1001];
    fill(dp,dp+1001,0);
    int ansv=0,answ=0;
    for(int i=0; i<n; i++) {
      for(int j=w; j>=0; j--) {
	if(dp[j] || j==0) {
	  if(j+a[i][1]<=w) {
	    dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]+a[i][0]);
	  }
	}
      }
    }
    for(int i=0; i<=w; i++) {
      if(dp[i]>ansv) {
	ansv=dp[i];
	answ=i;
      }
    }
    cout << "Case " << t << ":" << endl << ansv << endl << answ << endl;
    t++;
  }
  return 0;
}

C++: #include <cstdio>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <cfloat>

#include <map>

#include <utility>

#include <set>

#include <iostream>

#include <memory>

#include <string>

#include <vector>

#include <algorithm>

#include <functional>

#include <sstream>

#include <complex>

#include <stack>

#include <queue>

#include <numeric>

#include <cstring>



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

#define pb push_back



using namespace std;



typedef long long ll;

typedef pair<int, int> P;

typedef vector<int> vi;

typedef vector<vi> vvi;



const int INF = 1 << 29;

const double EPS = 1e-9;

const int MAX_N = 1000;

const int MAX_W = 1000;



int dp[MAX_N][MAX_W];

int dpw[MAX_N][MAX_W];

//int dpw[MAX_N + 1];



int main(){

	int n, cap, ans_c = 0;

	int v[MAX_N], w[MAX_N];

	

	while(1){

		memset(dp, 0 , sizeof(dp));

		memset(dpw, 0, sizeof(dpw));

		scanf("%d", &cap);

		if(cap == 0) break;

		scanf("%d", &n);



//		int dpw[n];

//		memset(dpw, 0, sizeof(dpw));



		rep(i, n){

			scanf("%d,%d\n",&v[i],&w[i]);

		}



		for(int i = 0; i < n; i++){

			for(int j = 0; j <= cap; j++){

				if(j < w[i]){

					dp[i+1][j] = dp[i][j];

					dpw[i+1][j] = dpw[i][j];

//					dpw[i+1] = dpw[i];

				}else{

					dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);

					if(dp[i+1][j] == dp[i][j - w[i]] +v[i]){

						dpw[i+1][j] = dpw[i][j-w[i]] + w[i];

//						dpw[i+1] = dpw[i] + w[i];

					}else{

						dpw[i+1][j] = dpw[i][j];

//						dpw[i+1] = dpw[i];

					}

				}

			}

		}

		ans_c++;

		printf("Case %d:\n%d\n%d\n", ans_c , dp[n][cap], dpw[n][cap]);

//		rep(i, n) cout << dpw[i] << endl;

	}

}

C++: #include <bits/stdc++.h>
using namespace std;

#define  req(i,r,k) for(int i=k;i<r;i++)
#define  rep(i,r) req(i,r,0)

const long long int INF = 100000000000000;

long long int dp[1002][1002];

int main() {

    for(int a=1;1;a++){
        int w,n;
        scanf(" %d",&w);
        if(w==0) break;
        scanf(" %d",&n);
        pair<int,int> t[n];
        char c;
        rep(i,n){
            scanf(" %d%c%d",&t[i].first,&c,&t[i].second);
        }

        rep(i,w){
            dp[0][i] = 0;
            dp[i][0] = 0;
        }

        dp[0][0] = 0;
        rep(i,n+1) {
            rep(j,w+1) {
                if(j >= t[i].second) {
                    dp[i+1][j] = max(dp[i][j], dp[i][j - t[i].second] + t[i].first);
                }
                else{
                    dp[i+1][j] = dp[i][j];
                }
            }
        }
        long long int maxvalue=0,thenweight=0;

        rep(i,w+1){
            //cout << dp[i] << " " << i << " " << thenweight << endl;
            if(maxvalue < dp[n][i]){
                maxvalue = dp[n][i];
                thenweight = i;
            }
        }

        //printf("Case %d:\n%lld\n%lld\n",a,maxvalue,thenweight);
        cout << "Case " << a << ':' << endl;
        cout << maxvalue << endl;
        cout << thenweight << endl;
    }
    return 0;
}