Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
	"fmt"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	Case := 1
	for {
		scanner.Scan()
		W, _ := strconv.Atoi(scanner.Text())
		if W == 0 {
			break
		}
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		w := make([]int, n+1)
		v := make([]int, n+1)
		for i := 1; i <= n; i++ {
			scanner.Scan()
			info := strings.Split(scanner.Text(), ",")
			v[i], _ = strconv.Atoi(info[0])
			w[i], _ = strconv.Atoi(info[1])
		}
		// fmt.Println(v)
		// fmt.Println(w)
		dp := make([][]int, n+1)
		for i := range dp {
			dp[i] = make([]int, W+1)
		}
		maxV := -(1 << 21)
		minW := 1 << 21
		for i := 1; i <= n; i++ {
			for j := 1; j <= W; j++ {
				// fmt.Println(dp)
				if j-w[i] >= 0 {
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
					if maxV < dp[i][j] {
						maxV = dp[i][j]
						minW = j
					} else if maxV == dp[i][j] {
						minW = min(minW, j)
					}
				} else {
					dp[i][j] = dp[i-1][j]
				}
			}
		}
		fmt.Printf("Case %d:\n", Case)
		Case += 1
		fmt.Println(maxV)
		fmt.Println(minW)
	}
}
func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;
 
#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back 
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int dp[1500][1500];

int solve(int i,int j){
  if(dp[i][j] != -1) return dp[i][j];

  int hoge;

  if(i == n) hoge = 0;

  else if(j < w[i]) hoge = solve(i+1, j);

  else hoge =  max(solve(i+1, j) , solve(i+1 , j - w[i]) + v[i]);

  return dp[i][j] = hoge;

}

int main(){

  while(1){
	int h;
	cin >> h;
	if(h == 0) break;

	int n;
	cin >> n;

	int v[1500],w[1500];

	REP(i,n){
	  cin >> v[i]>> w[i];
	}

	REP(i,1500) REP(j,1500) dp[i][j] = -1;

	cout << solve(0,h) << endl;

  }
}

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

int main(){
    int w, n;
    int count = 0;
    while(cin >> w, w){
        vector<pair<int, int> > v;
        long long dp[1010][1010];
        memset(dp, 0, sizeof(dp));
        cin >> n;
        for(int i=0; i < n; i++){int s, t; scanf("%d,%d", &s, &t); v.push_back(make_pair(s, t));}
        for(int i=n-1; 0 <= i; i--){
            for(int j=0; j <= w; j++){
                if(j < v[i].second) dp[i][j] = dp[i+1][j];
                else dp[i][j] = max(dp[i+1][j], dp[i+1][j-v[i].second]+v[i].first);
            }
        }
        cout << "Case " << ++count << ":" << 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 <cstdio>

using namespace std;

void rec(int n, int w, int &v, int &rw,
        const int W, const int N,
        const int lv[], const int lw[])
{
    v = rw = 0;
    if (n == N) {
        // not remain any treasure
        v = 0;
        rw = w;
    } else if (w < lw[n]) {
        // cannot pack treasure[n]
        rec(n + 1, w, v, rw, W, N, lv, lw);
    } else {
        int v1, v2, w1, w2;

        // through treasure[n]
        rec(n + 1, w        , v, rw, W, N, lv, lw);
        v1 = v;
        w1 = rw;
        // pack treasure[n]
        rec(n + 1, w - lw[n], v, rw, W, N, lv, lw);
        v2 = v + lv[n];
        w2 = rw - lw[n];

        // which is good
        if (v1 > v2) {
            v = v1;
            rw = w1;
        } else if (v1 < v2) {
            v = v2;
            rw = w2;
        } else {
            if (w1 >= w2) {
                v = v1;
                rw = w1;
            } else {
                v = v2;
                rw = w2;
            }
        }
    }
    // printf("  (%d, %d, %d, %d) -> (%d, %d)\n", n, w, v, rw, v, rw);
}

int main()
{
    for (int icase = 1;; ++icase) {
        int W, N;
        scanf("%d", &W);
        if (W == 0)
            break;
        scanf("%d", &N);

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

        int retv, retw;
        rec(0, W, retv, retw, W, N, v, w);

        printf("Case %d:\n%d\n%d\n", icase, retv, (W - retw) / 2);
    }

    return 0;
}

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

using namespace std;

#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,-1,sizeof(a))

int W, n;
int v[1002], w[1002];
int dp[1002][1002];

int rec(int i, int j) {
    if(dp[i][j] >= 0) return dp[i][j];

    int res = 0;
    if(i == n) {
        res = 0;
    } else if(j < w[i]) {
        res = rec(i+1, j);
    } else {
        res = max(rec(i+1,j), rec(i+1, j-w[i]) + v[i]);
    }

    return dp[i][j] = res;
}

int main() {
    for(int data = 1; ; data++) {
        ZERO(v); ZERO(w); MINUS(dp);
        scanf("%d", &W);
        if(W == 0) break;
        scanf("%d", &n);
        for(int i=0; i<n; i++) scanf("%d,%d", v+i, w+i);

        int ans = rec(0, W), wret = 0;
        while(dp[0][wret] != ans) wret++;
        printf("Case %d:\n", data);
        printf("%d\n", ans);
        printf("%d\n", wret-1);
    }
    return 0;
}

C++: #include <iostream>
#include <stdio.h>
#include <string>
using namespace std;


int main() {
  int dp[2][1001],n,k[1000],w[1000],i,j,h,kg,mk,mw,cn=0;
  while(true) {
	  cin >> kg;
	  if (kg==0) break;
	  for (i=0;i<=kg;i++) {dp[0][i]=0; dp[1][i]=0;}
	  cin >> n;
	  for (i=0;i<n;i++) scanf("%d,%d",&k[i],&w[i]);
	  for (i=0,j=0;i<n;i++) {
		  j=1-j;
		  for (h=kg;h>=0;h--)
			  if (h+w[i]>kg) dp[j][h]=dp[1-j][h];
			  else dp[j][h]=(dp[1-j][h+w[i]]+k[i])>dp[1-j][h] ? dp[1-j][h+w[i]]+k[i] : dp[1-j][h];
	  }
  mk=0;
  for (i=kg;i>=0;i--) if (mk<dp[j][i]) {mk=dp[j][i]; mw=i;}
  cn++;
  cout << "Case " << cn << ":" << endl;
  cout << mk << endl;
  cout << kg-mw << endl;
  }
 
  return 0;
}