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>
using namespace std;

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

C++: #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1000;
const int MAXW = 10000;

int val[MAXN],weight[MAXN];
int dp[MAXN][MAXW];
// dp[i][w] .. i番目までを重さwで行った時の最大の価値
// dp[i+1][w] =
//   max(dp[i][w-weight[i+1]] + val[i+1] , dp[i][w])
int main(){
  int N,W,casenum = 0;
  while(scanf("%d",&W) && W != 0){
    //input
    fill(*dp,*(dp+MAXN),0);
    scanf("%d",&N);
    for(int i = 0;i < N;i++){
      scanf("%d,%d",val+i,weight+i);
    }
    ///
    
    ///solve
    for(int i = 0; i < N;i++){
      for(int w = 0;w < W+1;w++){
        int use = (w - weight[i+1] > 0
                   ? dp[i][w - weight[i+1]] + val[i+1]
                   : 0);
        int unuse = dp[i][w];
        dp[i+1][w] = max(use,unuse);
      }
    }
    //
    printf("Case %d:\n",casenum);
    printf("%d\n",dp[N][W]);
    for(int w = 0;w <= W;w++){
      if(dp[N][w] == dp[N][W]){
        cout << w - 1<< endl;
        break;
      }
    }
    casenum++;
  }
}

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

using namespace std;

typedef long long ll;

ll value[1000], weight[1000];
ll dp[1001][1001]; // dp[?¬?????????????][??????] = ?????§??????

int main() {
	int W;
	int c = 1;
	while ( cin >> W, W ) {
		int N; cin >> N;
		for (int i = 0; i < N; ++i) scanf("%d,%d", &value[i], &weight[i]);

		for (int i = 0; i < 1001; ++i) {
			for (int j = 0; j < 1001; ++j) {
				dp[i][j] = 0;
			}
		}
//		fill(&dp[0][0], &dp[0][0]+1501*1501, 0);

		for (int i = 0; i < N; ++i) {
			for (int w = 0; w <= W; ++w) {
				dp[i+1][w] = max(dp[i+1][w], dp[i][w]);
				if (w + weight[i] <= W) {
					dp[i+1][w+weight[i]] = max(dp[i+1][w+weight[i]], dp[i][w]+value[i]);
				}
			}
		}
		ll av = 0, aw = 0;
		for (int w = 0; w <= W; ++w) {
			if (dp[N][w] > av) {
				av = dp[N][w];
				aw = w;
			}
		}
		printf("Case %d:\n", c++);
		printf("%d\n", av);
		printf("%d\n", aw);
	}
}

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){
            return 0;
        }
        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] = max(dp[i-1][j],dp[i-1][j - w[i-1]] + v[i-1]  );
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        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>
int max();
using namespace std;
int main()
{
    int W,n,w[1001],v[1001];
    int cnt = 1;
    int dp[1024][1000] = {{0}};
    for(;;){
        scanf("%d",&W);
        if(W == 0)break;
        scanf("%d",&n);
        for(int i = 1;i <= n; i++)scanf("%d,%d",&v[i],&w[i]);

        for(int j = 1;j <= n; j++){
            for(int i = 0;i <= W; i++){
                if(i < w[j]){
                    dp[i][j] = dp[i][j-1];
                }
                else {
                    dp[i][j] = max(dp[i][j-1],dp[i-w[j]][j-1]+v[j]);
                }
            }
        }
        int x = 0;
        for(int i = 0;i <= W; i++){
            if(dp[i][n] == dp[W][n]){
                x = i;
                break;
            }
        }
        printf("Case %d:\n",cnt);
        printf("%d\n",dp[W][n]);
        printf("%d\n",x);
        cnt++;
    }
    return 0;
}
int max(int a,int b){
    int x;
    x = (a > b) ? a:b;
    return x;
}

C++: #include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
#define pb push_back
#define MAX 100005
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;



signed main(){
  int W,N;
  int c=1;
  while(cin>>W>>N,W){
    vector<int> v(N),w(N);
    char x;
    vector<vector<int> > dp(N+1,vector<int>(W+1));
    rep(i,N)cin>>v[i]>>x>>w[i];
    loop(i,1,N+1){
      rep(j,W+1){
        if(j-w[i-1]>=0){
          dp[i][j]=max(dp[i-1][j-w[i-1]]+v[i-1],dp[i][j]);
        }else{
          dp[i][j]=dp[i-1][j];
        }
      }
    }
    int val=dp[N][W],wei;
    rep(i,W){
      if(dp[N][i]==val)wei=i;
    }
    cout<<"Case"<<c<<':'<<endl;
    cout<<val<<endl;
    cout<<wei<<endl;
    c++;
  }

  return 0;
}