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 <stdio.h>
#include <vector>
#include <string.h>

using namespace std;
int N;
vector<int> w;
vector<int> v;
int dp[1001][1001];

void solve()
{
	int W;
	int count = 1;
	while(cin >> W, W)
	{
		memset(dp, 0, sizeof(dp));
		cin >> N;
		w.resize(N);
		v.resize(N);
		for(int i = 0; i < N; ++i)
		{
			scanf("%d,%d", &v[i], &w[i]);
		}
		for(int i = 0; i < N; ++i)
		{
			for(int j = 0; j <= W; ++j)
			{
				if(j < w[i])
				{
					dp[i + 1][j] = dp[i][j];
				}
				else
				{
					dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
				}
			}
		}
		int pos = 0;
		for(int i = 0; i <= W; ++i)
		{
			if(dp[N][i] > dp[N][pos])
			{
				pos = i;
			}
		}
		cout << "Case " << count << ":" << endl;
		cout << dp[N][pos] << " " << pos << endl;
		++count;
	}
}

int main()
{
	solve();
	return(0);
}

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

using namespace std;

int dp[1000][1001],t[1000],w[1000];

int main(){
  for(int c=1;;c++){
    int n,q,i,j;
    scanf("%d",&q); if(q==0) break;
    scanf("%d",&n);

    for(i=0; i<n; i++)
      scanf("%d,%d",&t[i],&w[i]);

    for(i=0; i<=q; i++)
      dp[0][i] = (w[0]<i)?w[0]:0;

    for(i=1; i<n; i++)
      for(j=0; j<=q; j++){
	if(j+w[i]<=q)
	  dp[i][j+w[i]] = dp[i-1][j]+t[i];
	dp[i][j] = max(dp[i][j],dp[i-1][j]);
      }

    int mw=0,mt=0;
    for(j=0; j<=q; j++)
      if(dp[n-1][j]>mt){
	mt = dp[n-1][j];
	mw = j;
      }

    printf("Case %d\n%d\n%d\n",c,mt,mw);
  }
}

C++: #include<stdio.h>
int dp[1001][1001];
int main(void)
{
	int i,j,k,l;
	int w,n;
	int max;
	int a[1001],b[1001];
	
	scanf("%d",&w);
	l=1;
	while(w!=0){
		max=0;
	scanf("%d",&n);
		for(i=0;i<=n;i++){
			for(j=0;j<=w;j++){
				dp[i][j]=-1;
			}
		}
		for(i=0;i<n;i++){
			scanf("%d,%d",&a[i],&b[i]);
		}
		for(i=0;i<n;i++){
			dp[i][0]=0;	
			for(j=0;j<=w;j++){
				if(dp[i][j]!=-1){
					if(j+b[i]<=w && dp[i][j]+a[i]>=dp[i+1][j+b[i]]){
						dp[i+1][j+b[i]]=dp[i][j]+a[i];
					}
					if(dp[i+1][j]<dp[i][j]){
						dp[i+1][j]=dp[i][j];
					}
				}
			}
		}
		for(j=0;j<=w;j++){
			if(dp[n][j]>max){
				max=dp[n][j];
				k=j;
			}
		}
		printf("Case %d:\n",l);
		printf("%d\n%d\n",max,k);
		scanf("%d",&w);
		l++;
	}
	return 0;
}

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;
}