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>
#include<string>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack> 
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
const int MAX_V=105;
int INF = 1000000000;
  
int main(){
  int n=1;
  int W,N,i,j;
  while(  cin >> W ,W){
    cin >> N;
    int dp[N+1][W+1];
    rep(i,N+1){
      rep(j,W+1){
        dp[i][j]=0;
      }
    }

    rep(i,N){
      int v,w;
      char c;
      cin >> v >> c >> w;
      rep(j,W){
        dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
        if(j+w<W+1){
        dp[i+1][j+w]=max(dp[i][j]+v,dp[i+1][j+w]);
        }
      }
    }
    int value1=0;
    int weight=0;
    rep(j,W+1){
      if(dp[N][j]>value1){
        value1=dp[N][j];        
      }
    }
    rep(j,W+1){
      if(dp[N][j]==value1){
        weight=j;
        break;
      }
    }
    
    cout << "Case" << ' ' << n++ << ":" << endl;
    cout << value1 << endl;
    cout << weight << endl;  
    
  }
    return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int,int> P;

int main(){
	int W,N,cou=0;
	int tr[1001],we[1001];
	while(cin >> W , W){
		cou++;
		cin >> N;
		for(int i=1;i<=N;i++){
			scanf("%d,%d",&tr[i],&we[i]);
		}

		P dp[1001][1001];
		for(int i=0;i<=N;i++){
			for(int j=0;j<=N;j++){
				dp[i][j] = P(0,0);
			}
		}
		dp[0][0] = P(0,0);
		for(int i=1;i<=N;i++){
			dp[i][0] = P(0,0);
			for(int j=0;j<i;j++){
				if(dp[i-1][j].second+we[i] <= W){
					P p;
					p = P(dp[i-1][j].first+tr[i],dp[i-1][j].second+we[i]);
					if(p.first == dp[i-1][j].first){
						if(p.second < dp[i-1][j].second) dp[i][j+1] = p;
						else dp[i][j+1] = dp[i-1][j];
					}
					else if(p.first > dp[i-1][j].first){
						dp[i][j+1] = p;
					}
					else dp[i][j+1] = dp[i-1][j];
				}
				else dp[i][j+1] = dp[i-1][j];
			}
		}
		int ans1=0,ans2=0;
		for(int i=0;i<=N;i++){
			if(dp[N][i].first == ans1){
				if(dp[N][i].second < ans2) ans2 = dp[N][i].second;
			}
			else if(dp[N][i].first > ans1){
				ans1 = dp[N][i].first;
				ans2 = dp[N][i].second;
			}
		}

		cout << "Case " << cou << ":" << endl;
		cout << ans1 << endl;
		cout << ans2 << endl;
	}
}

C++: #include<iostream>
#include<stdio.h>

int dp[1000][10000];
int W;
int n;
int v[1000], w[1000];
int now = 1;

int main()
{
	while( 1 ){
		std::cin >> W;
		if( !W ) break;
		std::cin >> 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] = std::max( dp[i][j], dp[i][j-w[i]] + v[i] );
				}
			}
		}
		
		int res = W;
		for( int i = 0; i <= W; i++ ){
			if( dp[n][i] == dp[n][W] ) res = std::min( res, i );
		}
		
		std::cout << "Case " << now << ":" << std::endl;
		std::cout << dp[n][W] << std::endl;
		std::cout << res << std::endl;
		
		now++;	
	}
	

 	return 0;
}

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

long long dp[1001][1000];
int main(){
	int w, cntcase = 1;
	while (cin >> w, w){
		int n, treas_val[1000], treas_w[1000], ans_w = 0;
		long long ans_val = 0;
		cin >> n;
		for (int i = 0; i <= n; i++)for (int j = 0; j < w; j++) dp[i][j] = -1;
		dp[0][0] = 0;
		for (int i = 0; i < n; i++){
			scanf("%d,%d", &treas_val[i], &treas_w[i]);
		}
		for (int i = 0; i < n; i++){
			for (int j = 0; j < w; j++){
				if (dp[i][j] != -1){
					if (j + treas_w[i] < w
						&& dp[i + 1][j + treas_w[i]] < dp[i][j] + treas_val[i])
						dp[i + 1][j + treas_w[i]] = dp[i][j] + treas_val[i];
					if (dp[i][j] > dp[i + 1][j])
						dp[i + 1][j] = dp[i][j];
				}
				//printf("%d ", dp[i][j]);
			}
			//puts("");
		}
		for (int i = 0; i < w; i++){
			if (ans_val < dp[n][i]){
				ans_val = dp[n][i];
				ans_w = i;
			}
		}
		printf("Case %d:\n%d\n%d\n", cntcase, ans_val, ans_w);
		cntcase++;
	}
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<climits>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; i++)
#define FOR(i, j, k) for(int i = j; i < k; i++)
#define P pair<int, int>
const int INF = INT_MAX / 2;

int main(){
    int w, c = 1;
    while(cin >>w && w){
        cout <<endl;
        int n;
        cin >>n;
        vector< vector<int> > dp(n + 1, vector<int>(w + 1));
        REP(i, dp.size()){
            REP(j, dp[i].size()){
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 0;
        //input begin
        vector<P> j(n + 1);
        string str;
        getline(cin, str);
        FOR(i, 1, n + 1){
            getline(cin, str);
            stringstream ss(str);
            int a, b;
            char c;
            ss >>a >>c >>b;
            j[i].first = a;
            j[i].second = b;
        }
        //input end

        FOR(i, 1, dp.size()){
            int value = j[i].first, weight = j[i].second;
            REP(j, dp[i].size()){
                if(j >= weight && j - weight >= 0){
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value);
                } else{
                    dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                }
            }
        }

        int ans_v = -1, ans_w;
        REP(i, dp[0].size()){
            if(dp[n][i] > ans_v){
                ans_v = dp[n][i];
                ans_w = i;
            }
        }
        cout <<"Case " <<c <<":" <<endl <<ans_v <<endl <<ans_w;
        c++;
    }
    return 0;
}