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>

int solve (int);

int main(int argc, char const* argv[])
{
    int times = 0;

    while (true) {
        if(solve(++times) == 1) break;
    }
    return 0;
}

int solve(int times) {
    int max_weight, item_count;
    int prices[1000] = {0};
    int weights[1000] = {0};

    std::cin >> max_weight;
    if (max_weight == 0) return 1;

    std::cin >> item_count;

    for(int i = 0; i < item_count; i++) {
        int p, w;
        char c;
        std::cin >> p >> c >> w;

        prices[i]  = p;
        weights[i] = w;
    }

    int dp[1010] = {0};


    for (int i = 0; i < item_count; i++) {
        if (dp[weights[i]] == 0) {
            dp[weights[i]] = prices[i];
        } else {
            dp[weights[i]] = std::max(dp[weights[i]], prices[i]);
        }

        for (int j = 1; j < 1001; j++) {
            if (dp[j] == 0) continue;
            if (j == weights[i]) continue;

            int plus_weight = j + weights[i];
            int plus_price  = dp[j] + prices[i];
            if (plus_weight >= max_weight) continue;
            if (plus_weight >= 1001) continue;
            dp[plus_weight] = std::max(dp[plus_weight], plus_price);
        }
    }

    int min_weight = 99999;
    int max_price  = 0;
    for (int i = 0; i <= max_weight; i++) {
        if (max_price < dp[i]) {
            max_price  = dp[i];
            min_weight = i;
        } else if (max_price == dp[i]) {
            min_weight = std::min(i, min_weight);
        }
    }

    std::cout << "Case " << times << ":" << std::endl;
    std::cout << max_price << std::endl;
    std::cout << min_weight << std::endl;

    return 0;
}

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

struct pre{ int v, w; };

int max(int a, int b){
	return (a > b)? a : b;
}

int main(){
	const int MAX_N = 1000, MAX_W = 1000;
	int N, W;
	pre dat[MAX_N];
	int dp[MAX_N][MAX_W + 1];
	int p;
	
	for(int n = 1;; n++){
		scanf("%d", &W);
		if(W == 0) break;
		scanf("%d", &N);
		for(int i = 0; i < N; i++) scanf("%d,%d", &dat[i].v, &dat[i].w);
		
		for(int i = 0; i < MAX_N; i++){
			for(int j = 0; j < MAX_W; j++){
				dp[i][j] = 0;
			}
		}
		
		for(int i = dat[0].w; i <= W; i++) dp[0][i] = dat[0].v;
		for(int i = 1; i < N; i++){
			for(int j = 0; j <= W; j++){
				dp[i][j] = max((dat[i].w <= j)? dp[i - 1][j - dat[i].w] + dat[i].v : 0, dp[i - 1][j]);
			}
		}
		
		for(int i = 0; i <= W; i++){
			if(dp[N - 1][i] == dp[N - 1][W]){
				printf("Case %d:\n%d\n%d\n", n, dp[N - 1][W], i);
				break;
			}
		}
	}
	
	return 0;
}

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

const int MAX_N = 1001;
const int MAX_W = 10001;

int t;
int n, W;
int v[MAX_N], w[MAX_N];

int dp[MAX_N][MAX_W];

int main() {
	while (1) {
		std::cin >> W;
		if (w == 0)
			break;
		std::cin >> n;
		char ch;
		for (int i = 1; i <= n; ++i)
			std::cin >> v[i] >> ch >> w[i];
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j <= W; ++j)
				dp[i][j] = 0;
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j <= W; ++j) {
				if (w[i] > j)
					continue;
				dp[i][j] = std::max(dp[i - 1][j - w[i]] + v[i], dp[i][j]);
			}
		}
		int max = 0, maxv;
		for (int i = 0; i <= W; ++i) {
			if (max < dp[n][i]) {
				maxv = i;
				max = dp[n][i];
			}
		}
		++t;
		std::cout << "Case " << t << ':' << std::endl;
		std::cout << max << std::endl << maxv << std::endl;
	}
	return 0;
}

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

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

using namespace std;

int main(){
	int c = 1;
	int w;
	while(cin >> w && w){
		int n;
		int tr[1024][2];
		// 価値を最大に
		// 重さ合計 価値
		int dp[1024];
		
		cin >> n;
		rep(i, n){
			scanf("%d, %d", &tr[i][0], &tr[i][1]);
		}

		rep(i, w + 1){
			dp[i] = -1;
		}
		
		dp[0] = 0;
		rep(i, n){
			for(int j = w; j >= 0; j--){
				if(dp[j] != -1){
					int we = j + tr[i][1];
					if(we <= w){
						dp[we] = max(dp[we], dp[j] + tr[i][0]);
					}
				}
			}
		}
	
		int mv,mw;
		mv = 0; mw = 0;
		rep(i, w){
				if(dp[i] > mv){
					mv = dp[i];
					mw = i;
				}
		}

		cout << "Case " << c << ':' << endl;
		cout << mv << endl;
		cout << mw << endl;

		c++;
	}
	return 0;
}

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