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 <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define FOR(I,F,N) for(int I = F; I < (int)(N); I++)
#define rep(i, n) FOR(i, 0, n)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 28)

template<typename T>
void remove(vector<T>& vector, unsigned int index){
vector.erase(vector.begin() + index);
}

typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int W, N;
int tres[1001];
int weig[1001];
int maxW, maxV;
int dp[1001][1001];

void dfs(int weight, int value, int index){
	if(weight > W)return;
	if(dp[weight][index]>value)return;
	dp[weight][index] = value;
	if(index == N){
		if(maxV < value){
			maxW = weight;
			maxV = value;
		}else if(maxV == value){
			if(maxW > weight){
				maxW = weight;
				maxV = value;
			}
		}
		return;
	}
	dfs(weight, value, index+1);
	dfs(weight+weig[index], value+tres[index], index+1);
}


int main(void){
	int cnt = 0;
	while(cin >> W, W){
		cnt++;
		cin >> N;
		maxW = 0;
		maxV = 0;
		//fill_n(tres, 1001, 0);
		//fill_n(weig, 1001, 0);
		rep(i,W){
			rep(j,N){
				dp[j][i] = -1;
			}
		}

		rep(i,N){
			int n, w;
			scanf("%d,%d", &n, & w);
			tres[i] = n;
			weig[i] = w;
		}

		dfs(0,0,0);
		cout << "Case " << cnt << ":" << endl;
		cout << maxV << endl << maxW << endl;
	}

	return 0;
}



int StrToInt(string s){
	stringstream ss;
	ss << s;
	int val;
	ss >> val;
	return val;
}
string IntToStr(int i){
	stringstream ss;
	ss << i;
	return ss.str();
}

C++: #include <bits/stdc++.h>

#define SIZE 300005
#define MOD 1000000007LL
#define INF INT_MAX / 3
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define FORALL(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FOREACH(i,c) for(auto (i) : (c))
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef valarray<int> Array;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cout<<a[i];if(i==a.size()-1)cout<<endl;else cout<<" ";}}
int gcd(int a,int b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
int lcm(int a,int b){return a==0||b==0?0:a*b/gcd(a,b);}

int W, N;
ll v[1010];
ll w[1010];
const int NMAX = 1000;
const int VMAX = 10000;
ll dp[NMAX*VMAX+10];

void solve()
{
  int NV = N*10000;
  fill_n(dp,NV+1,LLINF);
  dp[0] = 0;
  REP(i,N) DOWN(j,NV,v[i])
    dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
  DOWN(i,NV,0) if(dp[i] <= W)
  {
    printf("%d\n%lld\n",i,dp[i]);
    return;
  }
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  for(int i = 1; scanf("%d",&W), W; i++)
  {
    scanf("%d",&N);
    REP(i,N) scanf("%lld,%lld",&v[i],&w[i]);
    printf("Case %d:\n",i);
    solve();
  }
  return 0;
}

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

int a[1001] = { 0 };
int b[1001] = { 0 };
long w, n, mv, mw;
void solve(long W, long f, long sum) {
	f = min(f, n) + 1;
	for (int i = f; i < n; i++) {
		if (W - b[i] <= 0) {
			mw = max(w - W, mw);
			mv = max(sum, mv);
			return;
		}
		solve(W - b[i], f, sum + a[i]);
	}
}

int main() {
	int u = 0;
	while (scanf("%d", &w)) {
		if (w == 0) break;
		scanf("%d", &n);

		mv = mw = 0; u++;
		for (int i = 0; i < n; i++) {
			scanf("%d,%d", &a[i], &b[i]);
		}

		solve(w, -1, 0);
		printf("Case %d:\n%ld\n%ld\n", u, mv, mw);
	}
	return 0;
}

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

struct Data{
    int v,w;
    Data(){}
    Data(int _v,int _w){
        v=_v; w=_w;
    }
    bool operator <(const Data &a)const{
        if(v==a.v) return w>a.w;
        return v<a.v;
    }
    Data operator +(const Data &a)const{
        return Data(v+a.v,w+a.w);
    }
};

int N,W;
Data t[1000],memo[1000][1001];

Data latte(int n,Data st){
    if(st.w>W) return Data(-1,-1);
    if(n==N) return st;
    if(memo[n][st.w].v!=-1) return memo[n][st.w];
    memo[n][st.w] = max(latte(n+1,st+t[n]),latte(n+1,st));
    return memo[n][st.w];
}

int main(){
    for(int ds=1;cin>>W,W;ds++){
        cin>>N;
        for(int i=0;i<N;i++) scanf("%d,%d",&t[i].v,&t[i].w);
        fill_n((Data*)memo,1000*1001,Data(-1,-1));
        Data ans = latte(0,Data(0,0));
        printf("Case %d:\n%d\n%d\n",ds,ans.v,ans.w);
    }
}

C++: #include<cstdio>
#include<iostream>
#include<array>
using namespace std;
array<pair<int,int>,1001> pairs;
array<array<pair<int,int>,1001>,1001> m;
int main(){
  for(int caseNo=0;;caseNo++){
    int w; scanf("%d",&w);
    if(w==0) break;
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++){
      scanf("%d,%d",&pairs[i].first,&pairs[i].second);
    }
    for(int j=0;j<=w;j++){
      m[0][j].first=0;
      m[0][j].second=0;
    }
    for(int i=1;i<=n;i++){
      for(int j=0;j<=w;j++){
	if(pairs[i].second<=j){
	  if(m[i-1][j].first>m[i-1][j-pairs[i].second].first+pairs[i].first){
	    m[i][j].first=m[i-1][j].first;
	    m[i][j].second=m[i-1][j].second;
	  }else{
	    m[i][j].first=m[i-1][j-pairs[i].second].first+pairs[i].first;
	    m[i][j].second=m[i-1][j-pairs[i].second].second+pairs[i].second;
	  }
	}else{
	  m[i][j].first=m[i-1][j].first;
	  m[i][j].second=m[i-1][j].second;
	}
      }
    }
    printf("Case %d:\n%d\n%d\n",caseNo+1,m[n][w].first,m[n][w].second);
  }
}

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

struct treasure{
	int value;
	int weight;
};

bool comp(treasure t1, treasure t2){
	if(t1.weight <= t2.weight) return true;
	else return false;
}

int main(){
	int w;
	const int maxw = 10000;
	int count = 1;
	while(cin >> w){
		if(w == 0) break;
		int n;
		int cost[maxw + 1];
		int best[maxw + 1];
		for(int i = 0; i <= maxw; i++){
			cost[i] = 0;
			best[i] = 0;
		}
		vector<treasure> treasures;
		cin >> n;
		for(int i = 0; i < n; i++){
			treasure t;
			char c;
			cin >> t.value >> c >> t.weight;
			treasures.push_back(t);
		}
		sort(treasures.begin(), treasures.end(), comp);
}
	return 0;
}