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

#define ll (long long)
#define REP(i,n) for(int i = 0;i<(int)n;i++)
#define FOR(i,a,b) for(int i = (a);i < (b);i++)
#define RFOR(i,a,b) for(int i = (a);i>(b);i--)

using namespace std;

/*thief??????*/

int main(void){
    
    /*(x,y) = (??????,??????)*/
    int dp[1001][1001] = {0};
    int w[1001] = {0},v[1001] = {0};
    int endurew;
    int number;
    int answer = 0;
    int casecounter = 1;
    while(cin >> endurew,endurew)
    {
        cin >> number;
        for(int i  =1; i<= number;i++)
            scanf("%d%*c%d",&v[i],&w[i]);
        
        for(int j = 1; j<= number;j++)
            for(int k = 0;k<=endurew;k++)
            {
              if(j == 1 && k>=w[j])
                  dp[j][k] = v[j];
              else if(k >= w[j])
                  dp[j][k] = v[j]+dp[j-1][k-w[j]];
              else
                  dp[j][k] = dp[j-1][k];
                
            }
        int max = 0;
        for(int i = 1;i<=endurew;i++)
        {
            if(max < dp[number][i])
            {
                answer = i;
                max = dp[number][i];
            }
            
        }
        cout << "Case" << casecounter<< ":" << endl << dp[number][answer]<< endl;
        cout << answer << endl;
        casecounter++;
    }
    return 0;
    
}

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

const int MAX_N = 1000;
const int MAX_W = 1000;
const int MAX_V = 10000;
int dp[MAX_N][MAX_W];
int w[MAX_N];
int v[MAX_N];

#define rep(i,a,b) for(int i=(a); i<(b); i++)

int N,W;

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

int findw(){
  int i = N - 1;
  int j = W;
  int ret = 0;
  while(i >= 0 && j >= 0){
    if(j >= w[i] && dp[i][j] < dp[i][j-w[i]] + v[i]){
      ret += w[i];
      j-=w[i];
    }
    i--;
    // printf("%d %d\n",i,j);
  }
  return ret;
}

int main(){
  int c=1;
  while(cin >> W , W){
    cin >> N;
    rep(i,0,N){
      scanf("%d,%d", &v[i], &w[i]);
    }
    memset(dp,0,sizeof(dp));
    printf("Case %d:\n%d\n%d\n", c++, solve(), findw());
  }

  return 0;
}

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

int dp[1000];
int main(){
	int w, n, ans_w = 0, ans_val = 0;
	for (int dataset = 1; cin >> w, w; dataset++){
		int t_w[1000], t_val[1000];
		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", &t_val[i], &t_w[i]);
			for (int j = w - 1; j >= 0; j--){
				//printf("%d ", dp[j]);
				if (dp[j] == -1 || j + t_w[i] >= w || dp[j + t_w[i]] > dp[j] + t_val[i])
					continue;
				dp[j + t_w[i]] = dp[j] + t_val[i];
			}
			//puts("");
		}
		for (int i = 0; i < w; i++){
			//printf("%d ", dp[i]);
			if (ans_val < dp[i]){
				ans_val = dp[i];
				ans_w = i;
			}
		}
		//puts("");
		printf("Case %d:\n%d\n%d\n", dataset, ans_val, ans_w);
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

#define  req(i,r,k) for(int i=k;i<r;i++)
#define  rep(i,r) req(i,r,0)

long long int dp[1001];

int main() {

    for(int a=1;1;a++){
        int w,n;
        scanf(" %d",&w);
        if(w==0) break;
        scanf(" %d",&n);
        pair<int,int> t[n];
        char c;
        rep(i,n){
            scanf(" %d%c%d",&t[i].first,&c,&t[i].second);
        }

        rep(i,w){
            dp[i] = 0;
        }

        dp[0] = 0;
        for(int i=0;i<n;i++) {
            for (int j = w; j != 0; j--) {
                if(j >= t[i].second) {
                    dp[j] = max(dp[j], dp[j - t[i].second] + t[i].first);
                }
            }
        }
        long long int maxvalue=0,thenweight=0;

        rep(i,w+1){
            //cout << dp[i] << " " << i << " " << thenweight << endl;
            if(maxvalue < dp[i]){
                maxvalue = dp[i];
                thenweight = i;
            }
        }

        printf("Case %d:\n%lld\n%lld",a,maxvalue,thenweight);
    }
    return 0;
}

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

int dp[1024][1024];

int main()
{
	int N,W,T=0;
	while(cin>>W, W)
	{
		cin >> N;

		int v,w; char c;
		for(int i=0; i<N; i++)
		{
			cin>>v>>c>>w;
			for(int j=0; j<=W-w; j++)
			{
				dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j]+v);
			}
		}

		int mi=W;
		for(int i=W; i>=0; i--)
		{
			if(dp[N][i]!=dp[N][mi])
			{
				cout << "Case " << ++T << ":\n";
				cout << dp[N][mi] << "\n" << mi << "\n";
				break;
			}
			mi=i;
		}
	}
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[1001][1001],wait[1001],value[1001];
void Initialization()
{
    for(int i=0;i<1001;i++)for(int j=0;j<1001;j++)dp[i][j]=-1;
}
int power(int n)
{
    int num=1;
    for(int i=1;i<=n;i++)num*=10;
    return num;
}
int serch(int i,int j,int n)
{
    int num;
    if(dp[i][j]>-1)return dp[i][j];
    else if(i==n)num=0;
    else if(j<wait[i])num=serch(i+1,j,n);
    else num=max(serch(i+1,j,n),serch(i+1,j-wait[i],n)+value[i]);
    return dp[i][j]=num;
}
int wserch(int i,int va,int ser,int n,int w)
{
    int num;
    if(i==n)num=w;
    else if(ser<va+value[i])num=wserch(i+1,va,ser,n,w);
    else if(ser==va+value[i])num=wait[i];
    else num=min(wserch(i+1,va,ser,n,w),wserch(i+1,va+value[i],ser,n,w)+wait[i]);
    return num;
}
int main()
{
    int n,w,point,num=1,wai,wa;
    string str;
    while(cin>>w&&w!=0){
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>str;
            value[i]=0;wait[i]=0;
            for(int j=0;;j++){
                if(str[j]==','){
                    for(int k=0;k<j;k++)value[i]+=power(j-k-1)*(str[k]-'0');
                    point=j;
                }
                if(str[j]=='\0'){
                    for(int k=point+1;k<j;k++)wait[i]+=power(j-k-1)*(str[k]-'0');
                    break;
                }
            }
        }
        Initialization();
        point=serch(0,w,n);
        wai=w;
        for(int i=0;i<n;i++){
            if(value[i]<point){
                wa=wserch(i+1,value[i],point,n,w)+wait[i];
                if(wa<wai)wai=wa;
            }
            else if(value[i]==point&&wai>wa)wai=wa;
        }
        cout<<"Case "<<num<<":\n"<<point<<endl<<wai<<endl;
        now++;
    }
}