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<stdio.h>
#include<algorithm>
using namespace std ;

int N,W ;
int m[1010][2] ;
int dp[1010][1010] ;
int cnt = 0 ;

int main(){
	
	while( cin >> W , W ){
		cin >> N ;
		cnt++;
		for( int i=0 ; i<1010 ; i++ )
			for( int j=0 ; j<1010 ; j++ )
				dp[i][j] = 0 ;
		
		for( int i=1 ; i<=N ; i++ ){
			scanf("%d,%d",&m[i][0] ,&m[i][1]) ;
		}
		
		
		for( int i=1 ; i<=N ; i++ ){
			for( int j=0 ; j<=W ; j++ ){
				if( j-m[i][1] >= 0 ){
					dp[i][j] = max( dp[i][j] , dp[i-1][j-m[i][1]] + m[i][0] ) ;
				}
			}
		}
		
		int best[2] = {} ;
		for( int j=0 ; j<=W ; j++ ){
			if( best[0] < dp[N][j] ){
				best[0] = dp[N][j] ;
				best[1] = j ;
			}
		}
		
		cout << "Case " << cnt << ':' << endl ;
		cout << best[0] << endl ;
		cout << best[1] << endl ;
	}
	
return 0;
}

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

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

C++: #define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#define W_MAX 1000
#define N_MAX 1000

int W, N;

int main(){
	int a = 1;
	while (1){
		int dp[N_MAX + 1][W_MAX + 1], w[N_MAX], v[N_MAX];
		scanf("%d", W, N);
		if (N == 0)
			break;
		for (int i = 0; i < N; ++i){
			scanf("%d %d", &v[i], &w[i]);
		}
		for (int i = 1; i < W; ++i)
			dp[0][i] = 0;
		for (int i = 1; i <= N; ++i){
			for (int j = 1; j <= W; ++j){
				if (j < w[i])
					dp[i][j] = dp[i - 1][j];
				else{
					dp[i][j] = std::max(dp[i-1][j], dp[i][j - w[i]] + v[i]);
				}
			}
		}
		int answ,minv=0;
		for (int i = 0; i <= W; ++i){
			if (dp[N][minv] < dp[N][i])
				minv = i;
		}
		printf("%d\n", "Case", a, ":");
		printf("%d\n", dp[N][W]);
		printf("%d\n", minv);
	}
	return 0;
}

C++: #include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iterator>
#include <cstdio>
#include <numeric>
using namespace std;
int main(){
  for(int tc = 1;; ++tc){
    int W;
    cin >> W;
    if(W == 0){
      break;
    }
    int n;
    cin >> n;
    int value[n], weight[n];
    for(int i = 0; i < n; ++i){
      scanf("%d,%d", &value[i], &weight[i]);
    }
    int table[n+1][W+1];    
    fill_n((int*)table, (n+1)*(W+1), 0);
    table[0][0] = 0; 
    for(int i = 0, j = 1; i < n; ++i, ++j){
      for(int w = 0; w <= W; ++w){
	if(table[i][w] != -1){
	  table[j][w] = table[i][w];
	}
      }
      for(int w = weight[i]; w <= W; ++w){
	int tmp = w - weight[i];
	if(table[i][tmp] >= 0){
	  table[j][w] = max(table[j][w], table[i][tmp] + value[i]);
	}
      }    
    }
    int ans_w = 0, ans_v = 0;
    for(int w = 0; w <= W; ++w){
      if(ans_v < table[n][w]){
	ans_v = table[n][w];
	ans_w = w;
      }
    }
    cout << "Case " << tc << ":" << endl;
    cout << ans_v << endl;
    cout << ans_w << endl;
  }
  return 0;
}

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

int data[1001][2];
int dp[1000][1000];
int n,w;

int solve(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=w;j++){
			if(j >= data[i][1]){
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-data[i][1]]+data[i][0]);
			}else{
				dp[i][j] =dp[i-1][1];
			}
		}
	}
	return dp[n][w];
}

int solve2(){
	for(int i=0;i<=w;i++){
		if(dp[n][w] == dp[n][i]){
			return i;
		}
	}
	return w;
}

int main(){
	int casecount = 0;
	while(true){
		casecount++;
		cin>>w;
		if(w == 0){
			break;
		}
		memset(dp,0,sizeof(dp));

		cin >> n;
		for(int i=1;i<=n;i++){
			scanf("%d,%d",&data[i][0],&data[i][1]);
		}
		
		cout << "Case " << casecount << ":" << endl;
		cout << solve() << endl;
		cout << solve2() << endl;
	}
}

C++: #include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=1234567;
const ll INF=1000000010;
const ll LINF=1000000000000000010LL;
const int MAX=10000010;
const double EPS=1e-3;
int dx[4]={0,1,0,1};
int dy[4]={0,0,1,1};
int dp[1010][1010];
int main(){
	int W;
	int c=0;
	while(cin>>W,W){
		int n;cin>>n;
		int v[1010],w[1010];
		memset(dp,0,sizeof(dp));
		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++)dp[i][j]=-INF;
		for(int i=0;i<n;i++)dp[i][0]=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<=W;j++){
				dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
				if(j+w[i]<=W){
					dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
				}
			}
		}
		int ans=0;
		int m=0;
		for(int i=0;i<=W;i++){
			if(ans<dp[n][i]){
				ans=dp[n][i];
				m=i;
			}
		}
		cout<<"Case "<<c<<":"<<endl;
		cout<<ans<<endl;
		cout<<m<<endl;
		c++;
	}
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int DP[1001][1001];
int main(){
	int W,N,C=0;
	while(cin>>W){
		if(!W) break;
		cin>>N;
		int v[1000],w[1000],SUMW=W;
		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) DP[i][j]=0;
		for(int i=0;i<N;++i){
			for(int j=0;j<=W;++j){
				if(w[i]>j){//入らない時
					DP[i+1][j]=DP[i][j];
				}else{//入る時
					DP[i+1][j]=max(DP[i][j],DP[i][j-w[i]]+v[i]);
				}
			}
		}
		for(int j=W;j>=0;--j) if(DP[N][W]==DP[N][j])SUMW=j;
		cout<<"case "<<++C<<":\n";
		cout<<DP[N][W]<<"\n"<<SUMW<<"\n";
	}
	return 0;
}