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 <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

const int INF = 1 << 29;
typedef pair<int, int> P;

int n, w;
int dp[1001][1001];//お宝の番号、重さ
int main(void)
{
	int caseCount = 0;
	while(cin >> w && w)
	{
		cin >> n;
		vector<int> ps(n), ws(n);
		memset(dp, 0, sizeof(dp));
		char c;
		for (int i = 0; i < n; i++)
		{
			cin >> ps[i] >> c >> ws[i];
		}

		if(ws[0] <= w) dp[0][ws[0]] = ps[0];
		for (int i = 1; i < n; i++)
		{
			for (int j = 0; j <= w; j++)
			{
				if(j + ws[i] <= w)
					dp[i][j + ws[i]] = max(dp[i - 1][j + ws[i]], dp[i - 1][j] + ps[i]);
			}
		}

		cout << "Case " << ++caseCount << ":" << endl;
		int ansp = 0, answ = INF;
		for (int i = 0; i <= w; i++)
		{
			if(ansp < dp[n - 1][i])
			{
				ansp = dp[n - 1][i];
				answ = i;
			}
		}
		cout << ansp << endl << answ << endl;
	}
	return 0;
}

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

using namespace std;

struct Treasure
{

  long value;
  long weight;
  bool flag;
};

int treasure_number = 0;
int limit_weight = 0;
Treasure result_treasure;

int AThief(vector<Treasure> &treasure,int total_value,int total_weight)
{

  if(limit_weight < total_weight) return 0;
  else
    {

      for(int i = 0; i < treasure_number; i++)
        {

          if(treasure[i].flag)
            {

              total_value += treasure[i].value;
              total_weight += treasure[i].weight;
              treasure[i].flag = false;

              if(AThief(treasure,total_value,total_weight) == 0)
                {

                  total_value -= treasure[i].value;
                  total_weight -= treasure[i].weight;

                  if(result_treasure.value == total_value && result_treasure.weight > total_weight) result_treasure.weight = total_weight;
                  else if(result_treasure.value < total_value)
                    {
                      result_treasure.value = total_value;
                      result_treasure.weight = total_weight;
                    }

                }
              else
                {
                  total_value -= treasure[i].value;
                  total_weight -= treasure[i].weight;
                }

              treasure[i].flag = true;

            }

        }

    }

  return 1;

}


int main()
{

  int dummy;
  Treasure temp;
  int case_number = 0;
  long total_value = 0;
  long total_weight = 0;
  vector<Treasure> treasure;

  result_treasure.value = -1;
  result_treasure.weight = 2147483647;

  cin >> limit_weight;

  while(limit_weight!=0)
    {

      cin >> treasure_number;

      treasure.clear();

      for(int i = 0; i < treasure_number; i++)
        {

          scanf("%d,%d",&temp.value,&temp.weight);
          temp.flag = true;
          treasure.push_back(temp);

        }

      dummy = AThief(treasure,total_value,total_weight);

      case_number++;

      cout << "Case " << case_number << ":" << endl;
      cout << result_treasure.value << endl;
      cout << result_treasure.weight << endl;

      cin >> limit_weight;

    }

}

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

using namespace std;

const int Target = 10000;

int main( void )
{
	int map[1001], save[1001];
	int w, count;
	count = 1;
	while(cin >> w, w) {
		++w;
		for(int i=0; i < w; ++i) map[i] = save[i] = 0;
		int n, value, weight;
		cin >> n;
		scanf("%d,%d", &value, &weight);
		if(value <= Target)
			save[weight] = map[weight] = max(save[weight], value);
		for(int i=1; i < n; ++i) {
			scanf("%d,%d", &value, &weight);
			if(value > Target) continue;
			save[weight] = max(save[weight], value);
			for(int j=0; j < w; ++j) {
				if(map[j]) {
					int ww = j + weight;
					int vv = map[j] + value;
					if(ww < w && vv <= Target)
						save[ww] = map[j] + value;
					else
						save[j] = max(save[j], map[j]);
				}
			}
			for(int j=0; j < w; ++j) {
				map[j] = save[j]; save[j] = 0;
			}
		}
		int Max = 0, idx;
		for(int i=0; i < w; ++i) {
			if(Max < map[i]) {
				Max = map[i];
				idx = i;
			}
		}
		cout << "Case " << count++ << ':' << endl;
		cout << Max << endl;
		cout << idx << endl;
	}

	return 0;
}

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

pair<int, int> hoge(vector< pair<int, int> > &c, int i, int ww, int w, int v, pair<int, int> d[])
{
    if (i  == int(c.size()) || ww < w)
        return make_pair(w, v);
    else if (0 < i && d[i-1].first <= w && v < d[i-1].second)
        return make_pair(w, v);

    pair<int, int> c0, c1, c2;
    c1 = hoge(c, i+1, ww, w + c[i].first, v + c[i].second, d);
    c2 = hoge(c, i+1, ww, w, v, d);

    if (ww < c1.first) {
        c0 = c2;
    }
    else if (c1.second == c2.second) {
        c0 =  (c1.first < c2.first)? c1 : c2;
    }
    else {
        c0 =  (c1.second < c2.second)? c2 : c1;
    }
    return d[i] = c0;
}

int main(int argc, char const* argv[])
{
    int ww, nn;
    for(int i = 0;; ++i) {
        vector< pair<int, int> > container;
        cin >> ww;
        if (ww == 0)
            break;
        cin >> nn;
        for (int i = 0; i < nn; ++i) {
            int v, w;
            char c;
            cin >> v >> c >> w;
            container.push_back(make_pair(w, v));
        }
        pair<int, int> d[1000] = {};
        pair<int, int> r = hoge(container, 0, ww, 0, 0, d);
        cout << "Case " << i+1 << ":" << endl;
        cout << r.second << endl;
        cout << r.first  << endl;
    }
    
    return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1000][1000];
int main()
{
	int count=1,i,j,W,w,n;
	while(1)
	{
		memset(dp,0,sizeof(dp));
		cin >> W;
		if(W==0)break;
		cin >> n;
		int v[n],w[n];
		for(i=0;i<n;i++)
		{
			scanf("%d,%d",&v[i],&w[i]);
		}
		for(i=0;i<n;i++)
		{
			for(j=0;j<=W;j++)
			{
				if(w[i]>j)
					dp[i+1][j]=dp[i][j];
				else
					dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
			}
		}
		for(i=W;i>=0;i--)
		{
			if(dp[n][W]>dp[n][i])break;
		}
		cout << "Case " << count << ':' << endl << dp[n][W] << endl;
		cout << i+1 << endl;
		count++;
	}
	return 0;
}