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 <stdlib.h>

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;
    }
    
  }
  
}

void rec2(int i, const int weight, const int n, int v[], int w[], int *sum_w, int *sum_v, int **dp)
{
  if (dp[i][*sum_w] != -1) {
    
    *sum_v = dp[i][*sum_w];
  }
  else {
  if (i == n) {
    *sum_v = 0;
  }
  else {
    int tmpw, tmpv;
    tmpw = *sum_w;
    tmpv = *sum_v;
    
    int w1, v1, w2, v2;

    if (weight >= w[i] + tmpw) {
      *sum_w += w[i];
      
      rec2(1+i, weight, n, v, w, sum_w, sum_v,dp);

      w1 = *sum_w;
      v1 = *sum_v + v[i];
    } else { v1 = -1; w1 = -1; }
    *sum_w = tmpw;
    *sum_v = tmpv;

    rec2(1+i, weight, n, v, w, sum_w, sum_v, dp);

    w2 = *sum_w;
    v2 = *sum_v;

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

  dp[i][*sum_w] = *sum_v;
  }
}

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 **dp;

    dp = (int **)malloc(sizeof(int*)*(n+1));
    for (int i = 0; i < n+1; i++)
      dp[i] = (int *)malloc(sizeof(int)*(weight+1));

    for (int i = 0; i < n+1; i++)
      for (int j = 0; j < weight+1; j++)
	dp[i][j] = -1;
    
    
    int huroshiki, value;
    int *sum_w, *sum_v;

    huroshiki = 0;
    value = 0;
    sum_w = &huroshiki; sum_v = &value;

    
    
    rec2(0, weight, n, v, w, sum_w, sum_v, dp);
    
    cout << "Case " << count << ":" << endl;
    cout << value << endl;
    cout << huroshiki << endl;
    
    count++;
  }

  return 0;
}

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

using namespace std;

int N, W;

int v[1010], w[1010];

int dp[2][1010];

void solve() {
	memset(dp, 0, sizeof(dp));
	
	dp[0][0] = 0;
	for (int i = 0; i < N; i++) {
		int nw = i%2, nx = (i+1)%2;
		for (int j = 0; j <= W; j++) {
			dp[nx][j] = max( dp[nx][j], dp[nw][j] );
			if (j + w[i] <= W) dp[nx][ j + w[i] ] = max( dp[nw][ j + w[i] ], dp[nw][ j ] + v[i]);
		}
	}
	
	int ansv = 0, answ;
	for (int i=0; i<=W; i++) {
		if (ansv < dp[N%2][i]) {
			ansv = dp[N%2][i];
			answ = i;
		}
	}
	cout << ansv << endl;
	cout << answ << endl;
}

int main() {
	int cnum = 0;
	
	while (1) {
		cin >> W; if (W==0) break;
		cnum++;
		
		cin >> N;
		char c;
		for (int i=0; i<N; i++) cin >> v[i] >> c >> w[i];
		
		cout << "Case " << cnum << ":" << endl;
		
		solve();
	}
	
	return 0;
}

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<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-1][j] , dp[i-1][j-m[i][1]] + m[i][0] ) ;
				}
				else{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		
		int best[2] = {0} ;
		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<algorithm>
#include<cstdio>
using namespace std;

int dp[1000],w[1000],v[1000],a,n,t=0;

int main(){

  while(cin >> a, a){

    t++;
    cin >> n;

    fill(dp,dp+a+1,0);

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

    for(int i=0;i<n;i++){
      for(int j=a;j>=0;j--){
	if(j+w[i] <= a) dp[j+w[i]] = max(dp[j+w[i]],dp[j]+v[i]);
      }
    }

    int mv = 0;
    for(int i=0;i<=a;i++){
      if(dp[i] > dp[mv]) mv = i;
    }

    cout << "Case" << t << ":" << endl;
    cout << dp[mv] << endl << mv << endl;
  }

}