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 <cstring>
#define MAX_N 1000

using namespace std;

int W, N;
int maxValue = 0, maxWeight = 0;
int value[MAX_N], weight[MAX_N];

void dfs(int pos, int Wsum, int Vsum) {
    if(Wsum > W) return;
    maxValue = max(maxValue, Vsum);
    if(maxValue == Vsum) maxWeight = Wsum;
    if(pos >= N) return;
    
    dfs(pos + 1, Wsum + weight[pos], Vsum + value[pos]);
    dfs(pos + 1, Wsum, Vsum);
    return;
}

int main(void) {
    int no = 1;
    while(scanf("%d %d", &W, &N), W != 0) {
        for(int r = 0; r < N; r++) {
            scanf("%d,%d", &value[r], &weight[r]);
        }
        dfs(0, 0, 0);
        cout << "Case " << no++ << ":" << endl;
        cout << maxValue << endl << maxWeight << endl;
        maxValue = maxWeight = 0;
    }
    return(0);
}

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

using db = double;
using ll = long long;
using vi = vector <int>;
#define op operator
#define pb push_back

const int N = 1e3L + 11;
int dp[N][N];

int main() {
	ios :: sync_with_stdio(0);

	int W, n;
	int _ = 0;
	while(cin >> W && W) {
		cin >> n;
		_ ++;
		memset(dp, 0, sizeof dp);
		for(int i = 1; i <= n; i ++) {
			int v, w; char c;
			cin >> v >> c >> w;
			for(int j = 0; j <= W; j ++)
				dp[i][j] = dp[i - 1][j];
			for(int j = w; j <= W; j ++)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v);
		}
		cout << "Case " << _ << ":\n";
		cout << *max_element(dp[n], dp[n] + W + 1) << '\n';
		cout << max_element(dp[n], dp[n] + W + 1) - dp[n] << '\n';
	}

	return 0;
}

C++: #define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <climits>
#include <map>
#include <stack>
using namespace std;
#define M_PI 3.141592
#define toRad 2.0*M_PI/360.0
#define inin(x) int x;cin>>x;
#define all(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" "<<x<<endl;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define first second
#define second first
typedef pair<int, int> pii;
int w, n;
pii memo[1000][1200];
vector<pii> a;
pii dp(int num, int W)
{
	if (W > w)return pii(INT_MIN, INT_MAX);
	if (num == n)return pii(0, 0);
	if (memo[num][W].first != -1)return memo[num][W];
	pii ans;
	if (dp(num + 1, W).first == dp(num + 1, W + a[num].second).first + a[num].first)
	{
		if (dp(num + 1, W).second < dp(num + 1, W + a[num].second).second)
		{
			ans = dp(num + 1, W);
		}
		else
		{
			pii p = dp(num + 1, W + a[num].second);
			p.first += a[num].first;
			p.second += a[num].second;
			ans = p;
		}
	}
	else if (dp(num + 1, W).first > dp(num + 1, W + a[num].second).first + a[num].first)
	{
		ans = dp(num + 1, W);
	}
	else
	{
		pii p = dp(num + 1, W + a[num].second);
		p.first += a[num].first;
		p.second += a[num].second;
		ans = p;

	}
	return memo[num][W] = ans;
}

int main()
{
	int Case = 0;
	while (cin >> w&&w&&++Case)
	{
		memset(memo, -1, sizeof memo);
		a.clear();
		cin >> n;
		rep(i, n)
		{
			pii x;
			scanf("%d,%d", &x.first, &x.second);
			a.push_back(x);
		}
		sort(all(a));
		pii val = dp(0, 0), wei;
		cout << "Case " << Case << ":" << endl;
		cout << val.first << endl << val.second << endl;
	}
}

C++: 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

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

int main(void) {
  int i,j;
  int w,n;
  int t=0;
  while(1){
    t++;
    cin>>w;
    if(w==0)break;
    cout<<"Case "<<t<<":"<<endl; 
    cin>>n;
    vector<vi> dp(n+1,vi(w+1,-1));
    dp[0][0]=0;
    rep(i,n){
      int tv,tw;
      char c;
      cin>>tv>>c>>tw;
      rep(j,w+1)if(dp[i][j]>=0){
	dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
	if(j+tw<=w)
	  dp[i+1][j+tw]=max(dp[i+1][j+tw],dp[i][j]+tv);
      } 
    }
    int ans=0;
    rep(i,w+1)if(dp[n][i]>dp[n][ans])ans=i;

    cout<<dp[n][ans]<<endl;
    cout<<ans<<endl;
   
  }
}

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

using namespace std;

int MAX = 1000*1000;

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 <cstdio>
#include <cstring>
#define max(a,b) a>b?a:b
#define N_MAX 1000
int main() {
    int w, n, cnt = 1;
    int val[N_MAX],g[N_MAX],dp[N_MAX+1];

    while (scanf("%d%d", &w, &n), w){
        for (int i = 0; i < n; i++) {
            scanf("%d,%d", val+i, g+i);
        }
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        for (int i = 0; i < n; i++){
            for (int j = w-g[i]; j>= 0; j--)
                if (dp[j]>=0) dp[j+g[i]] = max(dp[j+g[i]], dp[j]+val[i]);
        }
        int p = 0, q = 0;
        for (int i = 0; i <= w; i++) {
            if (dp[i]>p) {
                p = dp[i];
                q = i;
            }
        }

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

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

int w, n, cnt;
int a[1111], b[1111];
int dp[11111];

int main(){

  while(cin >> w, w){
    cin >> n;
    
    for(int i=0;i<n;i++) scanf("%d,%d", &a[i], &b[i]);

    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)
      for(int j=w;j>=0;j--)
	dp[j+b[i]] = max(dp[j]+a[i], dp[j+b[i]]);
    
    int ans = 0;
    for(int i=0;i<=w;i++)
      if(dp[i] > dp[ans]) ans = i;
    
    printf("Case %d:\n%d\n%d", ++cnt, dp[ans], ans);
  }

}