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 <cstring>
#include <utility>

using namespace std;

pair<int, int> max(const pair<int, int> &a, const pair<int, int> &b) {
    if (a.first == b.first ? a.second < b.second : a.first > b.first) {
        return a;
    } else {
        return b;
    }
}

#define MAX_W 1001

int main() {
    int W;
    int case_n = 1;
    while (cin >> W, W != 0) {
        int N; cin >> N;
        pair<int, int> dp[N][W+1];
        for (int i = 0; i < N; i++) 
            for (int j = 0; j <= W; j++) 
                dp[i][j] = pair<int, int>(0, 0); // 価値、 重さ
        int value[N];
        int weight[N];
        for (int i = 0; i < N; i++) {
            scanf("%d,%d", value+i, weight+i);
        }

        for (int j = weight[0]; j <= W; j++) {
            dp[0][j] = make_pair(value[0], weight[0]);
        }
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= W; j++) {
                if (j < weight[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = max(dp[i-1][j], 
                            make_pair(dp[i-1][j-weight[i]].first + value[i], 
                                      dp[i-1][j-weight[i]].second + weight[i]));
                }
            }
        }

        cout << "Case " << case_n << ":" << endl;
        cout << dp[N-1][W].first << endl;
        cout << dp[N-1][W].second << endl;
        case_n++;
    }
    return 0;
}

C++: #include<stdio.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<string.h>
#include<map>
#include<queue>

using namespace std;

typedef pair<int,int> pii;

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<=k;i++)
#define in(i,j,k) ((i)>=(j)&&(i)<=(k))

int dp[1000][1000];

int main(){
	int n,W,v[1000],w[1000],c=0,ans,we;
	for(;;){
		scanf("%d",&W);
		if(!W)break;
		scanf("%d",&n);
		ans=0;
		we=1023;
		rep(i,n)scanf("%d,%d",v+i,w+i);
		rep(i,n)rep(j,W)dp[j][i]=0;
		reps(i,1,W-1){
			reps(j,1,n-1){
				if(w[j]<=i)dp[i][j]=max(dp[i-1][j-1],dp[i-w[j]][j-1]+v[j]);
				else dp[i][j]=dp[i][j-1];
				ans=max(ans,dp[i][j]);
			}
		}
		for(int i=0;i<W&&we==1023;i++)rep(j,n)if(dp[i][j]==ans){we=i;break;}
		printf("Case %d:\n%d\n%d\n",++c,ans,we);
	}
	return 0;
}

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

int main()
{
	int W,N,c=1;
	char ch;
	while (cin >> W, W)
	{
		cin >> N;
		int a[N], w[N];
		for (int i=0; i<N; i++)
			cin >> a[i] >> ch >> w[i];

		int dp[W+1];
		for (int i=0; i<=W; i++)
			dp[i] = -1;

		dp[0] = 0;
		for (int i=0; i<N; i++)
		for (int k=W; k>=0; k--)
			if (dp[k] >= 0 && k+w[i] <= W)
				dp[k+w[i]] = max(dp[k]+a[i], dp[k+w[i]]);

		int MAX = 0;

		for (int i=1; i<=W; i++)
			if (dp[MAX] < dp[i])
				MAX = i;

		cout << "Case " << c++ << ':' << endl;
		cout << dp[MAX] << endl;
		cout << MAX << endl;
	}
}

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

struct treasure{
	int value;
	int weight;
};

bool comp(treasure t1, treasure t2){
	if(t1.weight <= t2.weight) return true;
	else return false;
}

int main(){
	int w;
	const int maxw = 10000;
	int count = 1;
	while(cin >> w){
		if(w == 0) break;
		int n;
		int cost[maxw + 1];
		int best[maxw + 1];
		for(int i = 0; i <= maxw; i++){
			cost[i] = 0;
			best[i] = 0;
		}
		vector<treasure> treasures;
		cin >> n;
		for(int i = 0; i < n; i++){
			treasure t;
			char c;
			cin >> t.value >> c >> t.weight;
			treasures.push_back(t);
		}
		sort(treasures.begin(), treasures.end(), comp);
		for(int j = 0; j < n; j++){
			for(int k = 1; k <= w; k++)
				if(k >= treasures[j].weight)
					if(cost[k] < cost[k - treasures[j].weight] + treasures[j].value)
					{
						cost[k] = cost[k - treasures[j].weight] + treasures[j].value;
						best[k] = j;
					}
		}
		cout << "Case" << " " << count++ << ":" << endl;
	cout << total << endl;
	}
	return 0;
}

C++: #include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define SIZE(x) ((int)(x).size())
#define UQ(v) v.erase(unique(v,begin(),v,end()),v.end());
#define INF 11922960 
#define pb push_back 
int dxy4[5] = { 0,1,0,-1,0 };
int dxy8[9] = { 0,1,1,0,-1,1,-1,-1,0 };
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)




//vector< vector<int> > v (max1, vector<int>(max2) );
int main() {
	int n, W, count = 0;
	while (1) {
		count++;
		cin >> W >> n;
		if (!W) break;
		vector<vector<int>>dp(n+1, vector<int>(W+1, 0));
		vector<int> v(n + 1, 0);
		vector<int> w(n + 1, 0);


		 char s;
		rep(i, n) { cin >> v[i+1]>> s>>w[i+1]; }

		rep(i, (n+1)) {
			if (!i)continue;
			//cout << i << "-------" << endl;
			rep(j, W-w[i]+1) {
				dp[i][j] = max(dp[i - 1][j],dp[i][j]);
				dp[i][w[i] + j] = max(dp[i - 1][w[i] + j], dp[i - 1][j] + v[i]);
				//cout << dp[i][w[i]+j] << " ";
			}
			//cout << endl;
		}
		int umax = dp[n][W];
		rep(i, W + 1) {
			if (dp[n][i] == umax) {
				cout << "Case " << count <<":"<< endl<< umax << endl << i << endl;
				break;
			}
		}
	}
	return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int dp[1001],N,v[100],w[100],W;
signed main(){
    for(int l=1;;l++){
        fill(dp,dp+1001,0);
        /*fill(v,v+100,0);
        fill(w,w+100,0);*/
        cin>>W;
        if(W==0)break;
        cin>>N;
        for(int i=0;i<N;i++){
            scanf("%lld,%lld",&v[i],&w[i]);
        }
        for(int i=0;i<N;i++){
            for(int j=W;j>=w[i];j--){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        for(int i=W;i>=0;i--){
            if(dp[W]!=dp[i]){
                cout<<"Case "<<l<<":"<<endl<<dp[W]<<endl<<i+1<<endl;
                break;
            }
        }
    }
    return 0;
}