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 <utility>
#include <vector>
using namespace std;

pair<int, int> hoge(vector< pair<int, int> > &c, int i, int ww, int w, int v, pair<int, int> d[])
{
    if (i  == int(c.size()) || ww < w)
        return make_pair(w, v);
    else if (0 < i && d[i-1].first < w && v < d[i-1].second)
        return make_pair(w, v);

    pair<int, int> c0, c1, c2;
    c1 = hoge(c, i+1, ww, w + c[i].first, v + c[i].second, d);
    c2 = hoge(c, i+1, ww, w, v, d);

    if (ww < c1.first) {
        c0 = c2;
    }
    else if (c1.second == c2.second) {
        c0 =  (c1.first < c2.first)? c1 : c2;
    }
    else {
        c0 =  (c1.second < c2.second)? c2 : c1;
    }
    return d[i] = c0;
}

int main(int argc, char const* argv[])
{
    int ww, nn;
    for(int i = 0;; ++i) {
        vector< pair<int, int> > container;
        cin >> ww;
        if (ww == 0)
            break;
        cin >> nn;
        for (int i = 0; i < nn; ++i) {
            int v, w;
            char c;
            cin >> v >> c >> w;
            container.push_back(make_pair(w, v));
        }
        pair<int, int> d[1000] = {};
        pair<int, int> r = hoge(container, 0, ww, 0, 0, d);
        cout << "Case " << i+1 << ":" << endl;
        cout << r.second << endl;
        cout << r.first  << endl;
    }
    
    return 0;
}

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

using namespace std;

int W,N,c;
int w[1001],p[1001];
int dp[2][10001];

int main(void){
	while(scanf("%d", &W)&&W){
		int ans;
		scanf("%d", &N);
		for(int i = 1; i <= N; i++){
			scanf("%d,%d", &p[i], &w[i]);
		}
		for(int i = 1; i <= N; i++){
			for(int j = 1;j <= W; j++){
				if(j-w[i]<0)continue;
				dp[i%2][j] = max(dp[1-i%2][j],dp[1-i%2][j-w[i]]+p[i]);
			}
		}
		c++;
		printf("Case%2d:\n",c);
		printf("%d\n",dp[N%2][W]);
		for(int i = 0; i < W; i++){
			if(dp[N%2][W] == dp[N%2][W-i]){
				ans = i;
			}
		}
		printf("%d\n",W-ans);
		/*ツ渉可甘コツ可サ*/
		for(int i = 0; i < 1001; i++){
			w[i] = 0;
			p[i] = 0;
		}
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 10001; j++){
				dp[i][j] = 0;
			}
		}
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
  int n;
  int w;
  int k=1;
  while(cin >> w >> n, w) {
    int p[n], a[w];
    REP(i, n) {
      scanf("%d,%d", &p[i], &a[i]);
    }
    int dp[n+1][w+1];           // dp[i][j]:iツ氾板姪堋づ慊づづ個陛ウツづ、ツ重ツつウツづ個堕債和ツつェjツ暗按可コツづ個づつォツづ個催妥・
    memset(dp, 0, sizeof(dp));
    REP(i, n) {
      REP(j, w+1) {
        if (j<a[i])
          dp[i+1][j] = dp[i][j];
        else
          dp[i+1][j] = max(dp[i][j],dp[i][j-a[i]] + p[i]);
      }
    }
    printf("Case %d:\n", k++);
    cout << dp[n][w] << endl;
    cout << lower_bound(dp[n], dp[n]+w+1, dp[n][w])-dp[n] << endl;
  }
}

C++: #include <cstdio>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <cfloat>

#include <map>

#include <utility>

#include <set>

#include <iostream>

#include <memory>

#include <string>

#include <vector>

#include <algorithm>

#include <functional>

#include <sstream>

#include <complex>

#include <stack>

#include <queue>

#include <numeric>

#include <cstring>



#define rep(i, n) for(int i = 0; i < (n); i++)

#define pb push_back



using namespace std;



typedef long long ll;

typedef pair<int, int> P;

typedef vector<int> vi;

typedef vector<vi> vvi;



const int INF = 1 << 29;

const double EPS = 1e-9;

const int MAX_N = 1000;

const int MAX_W = 10000;



int dp[MAX_N + 1][MAX_W + 1];

int dpw[MAX_N + 1][MAX_W + 1];



int main(){

	int n, cap, ans_c = 0;

	int v[MAX_N], w[MAX_N];

	

	while(1){

		memset(dp, 0 , sizeof(dp));

		memset(dpw, 0, sizeof(dpw));

		scanf("%d", &cap);

		if(cap == 0) break;

		scanf("%d", &n);



		rep(i, n){

			scanf("%d,%d\n",&v[i],&w[i]);

		}



		for(int i = 0; i < n; i++){

			for(int j = 0; j <= cap; j++){

				if(cap < w[i]){

					dp[i+1][j] = dp[i][j];

					dpw[i+1][j] = dpw[i][j];

				}else if(j - w[i] >= 0){

					dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);

					if(dp[i+1][j] == dp[i][j - w[i]] +v[i]){

						dpw[i+1][j] = dpw[i][j-w[i]] + w[i];

					}else{

						dpw[i+1][j] = dpw[i][j];

					}

				}

			}

		}

		ans_c++;

		printf("Case %d:\n%d\n%d\n", ans_c , dp[n][cap], dpw[n][cap]);

	}

}

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

int main() {
  for(int tci = 0; ; tci++) {
    int W; scanf("%d", &W); if(!W) break;
    int N; scanf("%d", &N);
    static int v[10000],w[10000];
    for(int i = 0; i < N; i++) {
      scanf("%d,%d", v+i, w+i);
    }
    static int knap[1001][1001];
    for(int i = 0; i <= N; i++) fill(knap[i], knap[i]+W+1, 0);
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < w[i]; j++) {
        knap[i+1][j] = knap[i][j];
      }
      for(int j = w[i]; j <= W; j++) {
        knap[i+1][j] = max(knap[i][j],knap[i][j-w[i]]+v[i]);
      }
    }
    pair<int,int> mval(0,0);
    for(int j = 0; j <= W; j++) {
      mval = max(mval, make_pair(knap[N][j],-j));
    }
    printf("Case %d:\n%d\n%d\n", tci+1, mval.first, -mval.second);
  }
  return 0;
}