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 <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    if(a<b) swap(a, b);
    if(b==0) return a;
    return gcd(b, a%b);
}

int W, N, cnt=1;
const int MAX_W = 1000;
const int MAX_N = 1000;
int dp[MAX_N+1][MAX_W+1];
int w[MAX_N]; int v[MAX_N];
int main() {
    while(cin >> W, W){
        cin >> N;
        for(int i=0; i<N; ++i){
            scanf("%d,%d", &v[i], &w[i]);
        }
        int sum_w=0;
        dp[0][0] = 0;
        for(int i=N-1; i>=0; --i){
            for(int j=0; j<=W; ++j){
               if(j<w[i]){
                   dp[i][j] = dp[i][j];
               }else{
                   dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]]+v[i]);
               }
            }
        }
        for(int i=0; i<N; --i){
            for(int j=0; j<=W; ++j){
                if(dp[i][j]==dp[0][W]){
                    sum_w = j;
                    break;
                }
            }
            if(sum_w) break;
        }
        cout << "Case " << cnt << ":" << endl;
        cout << dp[0][W] << endl;
        cout << sum_w << endl;
        cnt++;
    }
    return 0;
}

C++: #include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>

#define rep(i,n) for(int i=0; i < n;i++)

using namespace std;

int dp[1001][1001];

vector<string> split(const string &str, char delim){
  vector<string> res;
  size_t current = 0, found;
  while((found = str.find_first_of(delim, current)) != string::npos){
    res.push_back(string(str, current, found - current));
    current = found + 1;
  }
  res.push_back(string(str, current, str.size() - current));
  return res;
}

int main()
{
	int count = 0;
	int W,n,ans;
	int w[1001],v[1001];

	while(cin >> W && W)
	{
		count++;
		memset(dp,0,sizeof(dp));
		cin >> n;
		rep(i,n)
		{
			string s;
			cin >> s;
			vector<string> _s = split(s,',');
			v[i] = atoi(_s[0].c_str());
			w[i] = atoi(_s[1].c_str());
		}

		for(int i=0;i< n ;i++)
		{
			for(int j = 0 ; j <= W; j++)
			{
				if(j < w[i])
				{
					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=0;j <= W ; j++)
		{
			if(dp[n][j] == dp[n][W])
			{
				ans = j;
				break;
			}
		}
		cout << "Case " << count << endl;
		cout << dp[n][W] << endl << ans << endl;
	
	}

	return 0;
}

C++: #include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
int W;//風呂敷の容量
int N;//お宝の数
int dp[1010][1010];//dp[i][j]品物i番目までで重さがj以下の最大の価値
int dpW[1010][1010];
int Wt[1010];
int Vt[1010];
int ansW;
int main()
{
  int k = 1;
  while(cin>>W,W){
    cin >>N;
    for(int i = 0;i <N;i++){
      int w,v;
      scanf("%d,%d",&v,&w);
      Vt[i] = v;
      Wt[i] = w;
    }
    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(j-Wt[i]>=0){
	  dp[i+1][j] =max(dp[i][j],dp[i][j-Wt[i]]+Vt[i]);
	}else{
	  dp[i+1][j] =dp[i][j];
	}
      }
  }
    ansW = 1;
    for(int j = 1;j <=W;j++){
      if(dp[N][ansW] <dp[N][j]){
	ansW =j;
      }
    }
    printf("Case %d:\n",k);
    k++;
    cout <<dp[N][W]<<endl;
    cout <<ansW<<endl;
  }
  return 0;
}

C++: #include <iostream>
#include <array>
#include <string>
#include <tuple>
#include <vector>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
//using ll = long long;

#define out(s) cout << (s) << endl;

int dp[1010][1010];

int main()
{
	int W, N;
	cin >> W;
	vector<tuple<int, int>> anss;
	int cnt = 1;
	while (W!=0)
	{
		cin >> N;
		memset(dp, -1, sizeof(dp));
		dp[0][0] = 0;
		for (size_t i = 0; i < N; i++)
		{
			int vi, wi;
			scanf("%d,%d", &vi, &wi);
			for (size_t n = 0; n <= W; n++)
			{
				if (dp[i][n] != -1) {
					dp[i + 1][n] = max(dp[i][n], dp[i + 1][n]);
					if (n + wi > W)continue;
					dp[i + 1][n + wi] = max(dp[i][n] + vi, dp[i][n]);
				}
			}
		}
		int dp_max = *max_element(dp[N], dp[N] + W + 1);
		int index = 0;
		for (size_t i = 0; i < W+1; i++)
		{
			if (dp_max == dp[N][i]) { index = i; break; }
		}
		cout << "Case " << cnt << ":" << endl;
		cout << dp_max << endl;
		cout << index << endl;
		cin >> W;
		cnt++;
	}

	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int mp[1001][1000];

int main(){
	int W;char c;
	for(int num = 0;cin >> W&&W;num++){
		int v[1000], w[1000], n;
		cin >> n;
		fill((int*)mp, (int*)(mp+n+1), 0);
		
		for(int i = 0;i < n;i++){
			cin >> v[i] >> c >> w[i];
			for(int j = 0;j < W+1;j++){
				if(j < w[i])mp[i+1][j] = mp[i][j];
				else mp[i+1][j] = max(mp[i][j], mp[i][j-w[i]]+v[i]);
			}
		}
		
		int ans = 0;
		for(int i = 1;i < W+1;i++){
			if(mp[n][i] > mp[n][ans])ans = i;
		}
		cout << "Case " << num+1 << ":" << endl;
		cout << mp[n][ans] << endl << ans << endl;
	}
	return 0;
}
/*
1
y eazqyp pnop pngtg ye obmpngt xmybp mr lygw
*/

C++: //57
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  int c=0;
  for(int W;cin>>W,W;){
    c++;
    int N;
    cin>>N;
    int val[1001];
    fill_n(val,1001,-1);
    val[0]=0;
    while(N--){
      int v,w;
      (cin>>v).ignore()>>w;
      for(int i=1000;i-w>=0;i--){
	if(val[i-w]>=0){
	  val[i]=max(val[i],val[i-w]+v);
	}
      }
    }
    int i;
    for(i=W;val[i]==val[i-1]&&i>=0;i--) ;
    cout<<"Case "<<c<<':'<<endl;
    cout<<val[i]<<endl;
    cout<<i<<endl;
  }
  return 0;
}