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>

using namespace std;

typedef long long ll;
typedef pair<int, int> duo;

#define TT template<typename T>
TT T    sq(T x){ return x*x; }
TT int  ubnd(vector<T>& v,T x){ return upper_bound(v.begin(), v.end(), x) - v.begin(); }
TT int  lbnd(vector<T>& v,T x){ return lower_bound(v.begin(), v.end(), x) - v.begin(); }
TT void sort(T& v){ sort(v.begin(), v.end()); }
TT void revs(T& v){ reverse(v.begin(), v.end()); }
TT void uniq(T& v){ sort(v); v.erase(unique(v.begin(), v.end()), v.end()); }
TT void show(T& v,char d=' ',char e='\n'){for(int i=0;i<v.size();++i)cout<<v[i]<<((i==v.size()-1)?e:d);}
TT void inpt(vector<T>& v,int n){ v.reserve(n);for(int i=0;i<n;++i){T x; cin>>x; v.push_back(x);} }
TT T    In(T& x){ cin >> x; return x; }

static inline void fast_io(){ ios::sync_with_stdio(0); cin.tie(0); }
static inline int in(){ int x; scanf("%d", &x); return x; }
static inline string instr(){ string x; cin >> x; return x; }
static const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
static const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};

int main()
{
  const int inf = -10e8;
  int case_no = 1;
  int W;
  while (W = in()){
    int dp[1024];
    fill(dp, dp + 1024, inf);
    
    int n = in();
    dp[0] = 0;
    for (int i = 0; i < n; i++){
      int v, w;
      scanf("%d,%d", &v, &w);
      for (int i = W; i >= w; i--){
        dp[i] = max(dp[i], dp[i - w] + v);
      }
    }
    int min_w = W;
    for (int i = W; i >= 0; i--){
      if (dp[min_w] <= dp[i]) min_w = i;
    }
    printf("Case %d:\n", case_no);
    printf("%d\n%d\n", dp[min_w], min_w);
    case_no++;
  }
  return (0);
}

C++: #include <iostream>

using namespace std;

void rec(int i, const int weight, const int n, int v[], int w[], int *sum_w, int *sum_v)
{
  //?????????
  if (i == n) {
    if (weight >= w[i] + *sum_w) {
      *sum_w += w[i];
      *sum_v += v[i];
    } 
    
  }
  //?????§?????????
  else {
    int tmpw, tmpv;
    tmpw = *sum_w;
    tmpv = *sum_v;
    
    int w1, v1, w2, v2;
    //?¢??????\??????
    if (weight >= w[i] + tmpw) {
      *sum_w += w[i];
      *sum_v += v[i];
      
      rec(i+1, weight, n, v, w, sum_w, sum_v);
      
      w1 =  *sum_w;
      v1 =  *sum_v;

    } else { v1 = 0; }
    
    *sum_w = tmpw;
    *sum_v = tmpv;
    
    //?¢??????\?????????
    rec(i+1, weight, n, v, w, sum_w, sum_v);
    
    if (weight >= *sum_w) {
      w2 = *sum_w;
      v2 = *sum_v;
    }

    if (v1 > v2) {
      *sum_w = w1;
      *sum_v = v1;
    } else {
      *sum_w = w2;
      *sum_v = v2;
    }
    
  }
  
}


int main(void)
{
  int count = 1;
  while (true) {
    
    int weight, n;
    cin >> weight;
    if (weight == 0) break;
    cin >> n;
    int v[n], w[n];
    char c;
    for (int i = 0; i < n; i++) cin >> v[i] >> c >> w[i];
    //??\?????????

    int huroshiki, value;
    int *sum_w, *sum_v;

    huroshiki = 0;
    value = 0;
    sum_w = &huroshiki; sum_v = &value;
    rec(0, weight, n, v, w, sum_w, sum_v);

    cout << "Case " << count << ":" << endl;
    cout << value << endl;
    cout << huroshiki << endl;
    count++;
  }

  return 0;
}

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

int dp[1001][1001];

int main()
{
	int c = 1;

	while(1)
	{
		for(int i = 0; i <= 1000; i++)
			for(int j = 0; j <= 1000; j++)
				dp[i][j] = 0;

		int w, n;
		cin>>w>>n;
		if(w == 0)break;
		int treasure[1000];
		int price[1000];

		for(int i = 0; i < n; i++)
			scanf("%d,%d", &price[i], &treasure[i]);

		for(int i = 0; i < n; i++){
			for(int j = 0; j <= w; j++){
				if(j < treasure[i])
					dp[i + 1][j] = dp[i][j];
				else
					dp[i + 1][j] = max(dp[i][j], dp[i][j - treasure[i]] + price[i]);
			}
		}
	
		int ansWeight;
		for(ansWeight = w - 1; w >= 0; ansWeight--)
			if(dp[n][w] > dp[n][ansWeight])break;
			
		cout << "Case" << c++ <<":"<<endl;
		cout << dp[n][w] << endl;
		cout << ansWeight + 1 << endl;
	}

	return 0;
}

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

using namespace std;
int N;
int W;
vector<int> takaraW;
vector<int> takaraK;
vector<int> olddp;
vector<int> dp;

int main(){
    int kl = 0;
    while(true){
        takaraK.clear();
        takaraW.clear();
        dp.clear();
        cin >> W;
        if(W==0) return 0;
        cin >> N;
        takaraK.resize(N);
        takaraW.resize(N);
        dp.resize(W+1);
        for(int i=0;i<N;i++){
            char comma;
            cin >> takaraK[i] >> comma >>  takaraW[i];
        }
        for(int i=0;i<N;i++){
            olddp = dp;
            for(int j=0;j<W;j++){
                int neww = takaraW[i]+j;
                int newk = takaraK[i]+olddp[j];
                int oldk = olddp[neww];
                if(neww > W) continue;
                if(oldk < newk){
                    dp[neww] = newk;
                }
            }
        }
        int mw=W+2,mk=-1;
        for(int i=0;i<=W;i++){
            if(mk < dp[i]){
                mk = dp[i];mw = i;
            }
        }
        cout << "Case " << kl++ << endl;
        cout << mk << endl;
        cout << mw << endl;
    }
    return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
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, int N) {
    cout << "Case " << caseId << ":" << endl;
    int dp[1001] = {}; // 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) {
        if (value < dp[i]) {
            value = dp[i];
            weight = i;
        }
    }
    cout << value << endl << weight << endl;
}

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