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<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<cstdio>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;




int main(){


    int W,N;
    char c;
    int times = 1;

    while(cin >> W){

        
        if(W == 0){
            break;
        }
        cin >> N;
        vector<int> v(N),w(N);
    
        REP(i,N){
            cin >> v[i] >> c >> w[i];
        }

        int dp[1010][1010];

        REP(i,1010){
            REP(j,1010){
                dp[i][j] = -INF;
            }
        }
        REP(i,1010){
            dp[0][i] = 0;
        }
        
        for(int i = 1;i <= N;i++){
            for(int j = 0;j <= W;j++){

                if(j < w[i-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j - w[i-1]] + v[i-1]  );
                }
            }
        }
        int weight = 0;
        int value = 0;
        for(int i = 0;i < W;i++){

            if(weight < dp[N][i]){
                weight = i;
                value = dp[N][i]; 
            }
        }

        printf("Case %d:\n%d\n%d\n",times,value,weight);


        times++;

    }
    


    return 0;

}

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

int dp[1005];

int main() {
    int n,w,t=1;
    while(scanf("%d", &w), w) {
        memset(dp, -1, sizeof(dp));
        scanf("%d", &n);
        dp[0] = 0;

        int v,x;
        for(int i=0; i<n; ++i) {
            scanf("%d,%d", &v,&x);
            for(int j=w; j>=0; --j) {
                if(dp[j] == -1 || j+x > w) continue;
                dp[j+x] = max(dp[j+x],dp[j]+v);
            }
        }

        int ans = 0,ai = 0;
        for(int j=0; j<=w; ++j) {
            if(ans < dp[j]) ai = j;
            ans = max(ans, dp[j]);
        }
        printf("Case %d:\n%d\n%d\n", t++, ans, ai);
    }
}

C++: #include<stdio.h>
int i,j,l;
int w;
int n;
int kati,omosa;//
int casecnt=0;
long long int dp[1010][1010];//dp[お宝の総数][お宝の重さ]
int main(void){
	scanf("%d",&w);
	while(w!=0){
		for(i=0;i<=n;i++){//初期化
			for(j=0;j<=w;j++){
				if(j>0){
					dp[i][j]=-1;
				}
				else {//最初は何も盗んでいない ここからどんどん盗んでいく
					dp[i][j]=0;
				}
			}
		}
		scanf("%d",&n);
		for(i=0;i<n;i++){//盗む予定のn個のお宝入力
			scanf("%d,%d",&kati,&omosa);
			for(j=0;j<=w;j++){
				if(dp[i][j]>=0){//何も盗んでいない、またはすでに盗んでいたら
					if(dp[i+1][j+omosa]<kati){//送り先より送り元の方が価値が高かったら
						dp[i+1][j+omosa]=dp[i][j]+kati;
					}
				}
			}
			for(j=0;j<=w;j++){
				if(dp[i+1][j]<dp[i][j]){
					dp[i+1][j]=dp[i][j];
				}
			}
		}
		/*for(i=0;i<=n;i++){//デバグ　
			for(j=0;j<=w;j++){
				printf("%d ",dp[i][j]);
			}
			printf("\n");
		}*/
		int maxkati=0,maxomosa=0;
		for(j=0;j<=w;j++){//一番大きな価値の組み合わせ、重さを出力
			if(maxkati<dp[n][j]){
				maxkati=dp[n][j];
				maxomosa=j;
			}
		}
		casecnt++;
		printf("Case %d:\n",casecnt);
		printf("%d\n",maxkati);
		printf("%d\n",maxomosa);
		scanf("%d",&w);
	}
	return 0;
}

C++: #include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std ;

int N , W ;
int v[1001] , w[1001] ;
int dp[1002][1002] ;
int ans1 , ans2 ;

void solve(){
	memset(dp,-1,sizeof(dp)) ;
	dp[0][0] = 0 ;
	ans1 = 0 ;
	ans2 = 0 ;
	
	for( int i=1 ; i<=N ; i++ ){
		for( int j=0 ; j<=W ; j++ ){
			if( dp[i-1][j] >= 0 ){
				if( dp[i][j] < dp[i-1][j] ) dp[i][j] = dp[i-1][j] ;
				if( j+w[i] < W ){
					dp[i][j+w[i]] = max( dp[i-1][j+w[i]] ,dp[i-1][j] + v[i] ) ;
				}
			}
		}
	}
	
	for( int i=0 ; i<W ; i++ ){
		if( ans1 < dp[N][i] ){
			ans1 = dp[N][i] ;
			ans2 = i ;
		}
	}
}

int main(){
	
	int t=0 ;
	
	while( cin >> W >> N , W ){
		for( int i=1 ; i<N ; i++ ){
			scanf("%d,%d" ,&v[i] ,&w[i] ) ;
		}t++ ;
		solve() ;
		
		cout << "Case " << t << ':' << endl ;
		cout << ans1 << endl ;
		cout << ans2 << endl ;
	}
	
return 0 ; 
}

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

int w, z[1100][2] = {}, map[1100][1100] = {}, n, min_w = 20000000, max_v = 0;

void ini(){
	for(int i = 0;i<1020;i++){
		for(int j = 0;j<1020;j++){
			map[i][j] = 0;
		}
	}
}

int main(){
	int k = 1;
	while(cin >> w >> n){
		if (w == 0) break;
		min_w = 20000000;
		max_v = -1;
		ini();
		for(int i = 1;i<=n;i++){
			char cmp;
			cin >> z[i][0] >> cmp >> z[i][1];
		}
		for(int i = 1;i<=n;i++){
			for(int j = 1;j<=w;j++){
				if (z[i][1] > j) continue;
				map[i][j] = max(map[i - 1][j], map[i - 1][j - z[i][1]] + z[i][0]);
			}
		}
		for(int i = w;i>0;i--){
			if (max_v <= map[n][i]) {
				max_v = map[n][i];
				min_w = i;
			}
		}
		cout << "Case " << k << ":" << endl
			<< max_v << endl
			<< min_w << endl;
		k++;
	}
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int tr[1100][2]={0},dp[1100][1100]={0};
int main(){
  for(int c=1;;c++){
    int w,n,ans = 0,q;
    cin >>w;
    if(w == 0) break;
    cin >>n;
    for(int i=0; i<1100; i++){
      tr[i][0] = tr[i][1] = 0;
      for(int j=0; j<1100; j++) dp[i][j] = 0;
    }
    for(int i=1; i<=n; i++) scanf("%d,%d",&tr[i][0],&tr[i][1]);
    for(int i=1; i<=n; i++){
      for(int j=0; j<=w; j++){
	if(j == 0) dp[i][tr[i][1]] = max(dp[i][tr[i][1]],tr[i][0]);
	if(j+tr[i][1]<=w && dp[i-1][j]!=0) dp[i][j+tr[i][1]] = max(dp[i][j+tr[i][1]],dp[i-1][j]+tr[i][0]);
      }
    }
    for(int i=0; i<=w; i++){
      if(ans<dp[n][i]){
	ans = dp[n][i];
	q = i;
      }
    }
    cout <<"Case "<<c<<":"<<endl<<ans<<endl<<q<<endl;
  }
  return 0;
}