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<stdio.h>
int a,b,c[1001][1001],d[1001],e[1001],m,mm,i,j,g=1;
int main(void)
{
	scanf("%d",&a);
	while(a!=0){
		m=0;
		mm=0;
		scanf("%d",&b);
		for(i=0;i<=b;i++){
			for(j=0;j<=a;j++){
				c[i][j]=-1;
			}
		}
		for(i=0;i<b;i++){
				scanf("%d,%d",&d[i],&e[i]);
		}
		c[0][0]=0;
		for(i=0;i<b;i++){
			for(j=0;j<=a;j++){
				if(c[i][j]>=0 && c[i][j]+d[i]>c[i+1][j+e[i]] && j+e[i]<=a){
					c[i+1][j+e[i]]=c[i][j]+d[i];
				}
				if(c[i][j]>=0 && c[i+1][j]<c[i][j]){
					c[i+1][j]=c[i][j];
				}
			}
			
		}
		for(j=0;j<=a;j++){
			if(c[b][j]>m){
				m=c[b][j];
				mm=j;
				//printf("c=%d j=%d\n",c[b][j],j);
			}
		}
		/*for(i=0;i<=b;i++){
			for(j=0;j<=a;j++){
				printf("%4d",c[i][j]);
			}
			printf("\n");
		}
		printf("%d\n",c[b][49]);*/
		printf("Case %d:\n%d\n%d\n",g,m,mm);
		g++;
		scanf("%d",&a);
	}	
	return 0;
}

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

using namespace std;

#define INF (1<<29)
#define mp make_pair
#define pb push_back

typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pii;

int main(){
	int W;
	for( int n = 1; cin >> W; n++ ){
		if( W == 0 ) break;
		int N;
		cin >> N;
		vi v(N), w(N);
		for( int i = 0; i < N; i++ ){
			scanf("%d,%d", &v[i], &w[i]);
		}
		// DP
		vector<vector<pii> > dp(N+1, vector<pii>(W+1,mp(0,0)));
		for( int i = 1; i <= N; i++ ){
			for( int j = 1; j <= W; j++ ){
				pii upperLeft = dp[i-1][j-w[i-1]], upper = dp[i-1][j];
				if( j-w[i-1] < 0 ){
					dp[i][j] = upper;
				}else{
					if( upper.first == upperLeft.first+v[i-1] ){
						dp[i][j] = mp(upper.first, min(upper.second, upperLeft.second+w[i-1]));
					}else if( upper.first < upperLeft.first+v[i-1] ){
						dp[i][j] = mp(upperLeft.first+v[i-1], upperLeft.second+w[i-1]);
					}else{
						dp[i][j] = upper;
					}
				}
			}
		}
		cout << "Case " << n << ":" << endl;
		cout << dp[N][W].first << endl;
		cout << dp[N][W].second << endl;
	}
}

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

int main(){
  int W,n,ans,count=1,weight,v[1001],w[1001];
  int dp[2][1000];
  
  while(cin>>W,W){
    fill(v,v+1001,0);
    fill(w,w+1001,0);
    fill(dp[0],dp[2],0);
    ans=0;
    
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>v[i];
      getchar();
      cin>>w[i];
    }
    
    for(int i=0;i<n;i++){
      for(int l=1;l<=W;l++){
        if(w[i]<=l)
          dp[1][l]=max(dp[0][l],dp[0][l-w[i]]+v[i]);
        else
          dp[1][l]=dp[0][l];
      }
      for(int z=0;z<=W;z++){
        dp[0][z]=dp[1][z];
        dp[1][z]=0;
      }
    }
    
    for(int i=0;i<=W;i++)
      if(dp[0][i]>ans){
        ans=dp[0][i];
        weight=i;
      }
    
    printf("Case %d:\n",count);
    printf("%d\n%d\n",ans,weight);
    count++;
  }
  return 0;
}

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

pair<int, int> hoge(vector< pair<int, int> > &c, int i, int ww, int w, int v, pair<int, int> d[])
{
    if (i  == int(c.size()) || ww < w)
        return make_pair(w, v);
    else if (0 < i && d[i-1].first < w && v < d[i-1].second)
        return make_pair(w, v);

    pair<int, int> c0, c1, c2;
    c1 = hoge(c, i+1, ww, w + c[i].first, v + c[i].second, d);
    c2 = hoge(c, i+1, ww, w, v, d);

    if (ww < c1.first) {
        c0 = c2;
    }
    else if (c1.second == c2.second) {
        c0 =  (c1.first < c2.first)? c1 : c2;
    }
    else {
        c0 =  (c1.second < c2.second)? c2 : c1;
    }
    return d[i] = c0;
}

int main(int argc, char const* argv[])
{
    int ww, nn;
    for(int i = 0;; ++i) {
        vector< pair<int, int> > container;
        cin >> ww;
        if (ww == 0)
            break;
        cin >> nn;
        for (int i = 0; i < nn; ++i) {
            int v, w;
            char c;
            cin >> v >> c >> w;
            container.push_back(make_pair(w, v));
        }
        sort(container.begin(), container.end(), greater< pair<int, int> >());
        pair<int, int> d[1000] = {};
        pair<int, int> r = hoge(container, 0, ww, 0, 0, d);
        cout << "Case " << i+1 << ":" << endl;
        cout << r.second << endl;
        cout << r.first  << endl;
    }
    
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

int MAX = 1010;

void solve(int n, int W, vector<int> v, vector<int> w) {
	int **dp = new int*[n];
	for (int i=0; i<n; i++) {
		dp[i] = new int[MAX+1];
		for (int j=0; j<MAX+1; j++)
			dp[i][j] = 0;
	}

	dp[0][w[0]] = v[0];
	for (int i=1; i<n; i++) {
		for (int j = 0; j<MAX+1; j++) {
			dp[i][j] = max(dp[i][j], dp[i-1][j]);
			if (j+w[i] <= W) dp[i][j+w[i]] = max(dp[i][j+w[i]], dp[i-1][j]+v[i]);
		}
	}

	int val = -1, weight = 0;
	for (int j=0; j<=W; j++) {
		if (val < dp[n-1][j]) {
			val = dp[n-1][j];
			weight = j;
		}
	}

	cout << val << endl << weight << endl;

	for (int i=0; i<n; i++)
		delete [] dp[i];
	delete [] dp;
}

int main() {
	

	int n, W;
	int ver = 1;

	cin >> W;
	while (W!=0) {
		cin >> n;

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

		cout << "Case " << ver << ":" << endl;
		solve(n, W, v, w);

		cin >> W;
		ver++;
	}

	return 0;
}

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

long long dp[1000];
int main(){
	long long w, n, ans_w = 0, ans_val = 0;
	for (int dataset = 1; cin >> w, w; dataset++){
		long long t_w, t_val;
		cin >> n;
		for (long long i = 0; i < w; i++) dp[i] = -1;
		dp[0] = 0;
		for (long long i = 0; i < n; i++){
			scanf("%lld,%lld", &t_val, &t_w);
			for (long long j = w - 1; j >= 0; j--){
				//printf("%d ", dp[j]);
				if (dp[j] == -1 || j + t_w >= w || dp[j + t_w] > dp[j] + t_val)
					continue;
				dp[j + t_w] = dp[j] + t_val;
			}
			//puts("");
		}
		for (long long i = 0; i < w; i++){
			//printf("%d ", dp[i]);
			if (ans_val < dp[i]){
				ans_val = dp[i];
				ans_w = i;
			}
		}
		//puts("");
		printf("Case %d:\n%lld\n%lld\n", dataset, ans_val, ans_w);
	}
	return 0;
}