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 <bits/stdc++.h>
#define rep(i,l,n) for(int i=l;i<n;i++)
#define rer(i,l,n) for(int i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

vi v,w;
int n;
int dp[1010][1010];

int solve(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=solve(i+1,j);
	else res=max(solve(i+1,j),solve(i+1,j-w[i])+v[i]);
	return dp[i][j]=res;
}

int main(){
	for(int l=1;;l++){
		int W,x,y;
		cin>>W;
		if(W==0) break;
		cin>>n;
		rep(i,0,n){
			scanf("%d,%d",&x,&y); v.pb(x); w.pb(y);
		}
		memset(dp,-1,sizeof(dp));
		int MAX=0,ans=0;
		rer(i,1,W){
			if(MAX<solve(0,i)){
				MAX=solve(0,i); ans=i;
			}
		}
		cout<<"Case"<<l<<":"<<endl; o(MAX); o(ans);
	}
}

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

using namespace std;

int main(){
	int w, n, p = 1;
	while(cin >> w, w){
		cin >> n;
		vector<pair<int, int> > t(n);
		for(int i=0; i< n; i++) scanf("%d,%d", &t[i].first, &t[i].second);
		long long dp[1010][1010];
		for(int i=0; i < 1010; i++) for(int j=0; j< 1010; j++) dp[i][j] = 0;
		for(int i=n-1; 0 <= i; i--){
			for(int j=0; j <= w; j++){
				if(j < t[i].second) dp[i][j] = dp[i+1][j];
				else dp[i][j] = max(dp[i+1][j], dp[i+1][j-t[i].second] + t[i].first);
			}
		}
		cout << "Case " << p++ << ":" << endl;
		cout << dp[0][w] << endl;
		for(int i = w; ; i--){
			if(dp[0][i] != dp[0][w]){cout << i+1 << endl; break;}
		}
	}
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <string>
#include <cmath>
#include <map> 
using namespace std;
 
const int MAX= 10000100;

#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define rep(i,a) loop(i,0,a)
#define all(a) (a).begin(),(a).end()
#define MAX_V 10000
#define MAX_W 10000
int W,N;
long int dp[MAX_V+1][MAX_W+1];
int w[MAX_W+1];
long int v[MAX_V+1];
void solve(){
  int cnt = 0;
  vector<int> data(N,0);
  for(int i = N - 1 ; i >= 0 ; i --){
    
    for(int j = 0 ; j <= W ; j ++){
      data[i]++;
      if(j<w[i]){
	  data[i]--;
	dp[i][j] = dp[i+1][j];
      }else {
	dp[i][j] = max(dp[i+1][j] , dp[i+1][j-w[i]] + v[i]);

	if(dp[i+1][j] < dp[i+1][j-w[i]] + v[i]){
	    data[i]--;
	}
      }
    }
  }
  rep(i,N){
    //cout<<data[i]<<endl;
    if(data[i]==0){
      cnt+= w[i];
    }
  }
  printf("%ld\n",dp[0][W]);
  cout<<cnt<<endl;
}

int main(void){
  int cnt = 0;
  while(cin>>W,W){
    cout<<"Case "<<++cnt<<":"<<endl;
    cin>>N;
    for(int i = 0 ; i < N ; i ++){
      scanf("%ld,%d",&v[i],&w[i]);
    }
    solve();
    
  }
  
}

C++: #include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
#include <random>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)

int caseId = 1;

void solve42(int W) {
    cout << "Case " << caseId << ":" << endl;
    int N;
    cin >> W >> N;
    int dp[1001] = {0}; // dp[i]: maxvalue under weight i
    REP(i,N) {
        int v, w;
        scanf("%d,%d", &v, &w);
        for(int j = W; j >= w; j--) {
            dp[j] = max(dp[j], dp[j-w] + v);
        }
    }
    int value = 0, weight = 0;
    REP(i,W+1) {
        if (value < dp[i]) {
            value = dp[i];
            weight = i;
        }
    }
    cout << value << endl << weight << endl;
}

int main() {
    int W;
    while (cin >> W, W) {
        solve42(W);
        caseId++;
    }
    return 0;
}

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

#define SIZE 300005
#define MOD 1000000007LL
#define INF 1 << 30
#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;
int v[1010];
int w[1010];

void solve()
{
  int dp[1010];
  fill_n(dp,1010,0);
  REP(i,N) DOWN(j,W,w[i])
    dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
  int ans1 = 0, ans2 = 0;
  DOWN(i,W,0) if(ans1 <= dp[i])
  {
    ans1 = dp[i];
    ans2 = i;
  }
  printf("%d\n%d\n",ans1,ans2);
}

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

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

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

using namespace std;

int main( void )
{
	int map[1001];
	int w; long long count;
	count = 0;
	while(cin >> w, w) {
		++w;
		for(int i=0; i < w; ++i) map[i] = 0;
		int n, value, weight;
		cin >> n;
		scanf("%d,%d", &value, &weight);
		map[weight] = value;
		for(int i=1; i < n; ++i) {
			scanf("%d,%d", &value, &weight);
			for(int j=w-1; j > 0; --j) {
				if(map[j]) {
					int ww = j + weight;
					if(w > ww) {
						map[ww] = max(map[ww], map[j] + value);
					}
				}
			}
			map[weight] = max(map[weight], value);
		}
		int Max = 0, idx;
		for(int i=1; i < w; ++i) {
			if(Max < map[i]) {
				Max = map[i];
				idx = i;
			}
		}
		cout << "Case " << ++count << ':' << endl;
		cout << Max << endl;
		cout << idx << endl;
	}

	return 0;
}