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<vector>
#include<string.h>
using namespace std;

int main(){
    int w,n,va,we;
    int dp[10000];
    char c;
    vector<pair<int,int> >vec;
    
    while(cin>>w>>n,w){
        for(int i=0;i<n;i++){
            cin>>va>>c>>we;
            vec.push_back(make_pair(va, we));
        }
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            int tv=vec[i].first, tw=vec[i].second;
            for(int j=w;j>=0;j--){
                if(tw+j<=w){
                    dp[tw+j]=max(dp[tw+j],dp[j]+tv);
                }
            }
        }
        int aw=0,av=0;
        for(int i=0;i<=w;i++) {
            if(dp[i]>av){
                aw=i;
                av=dp[i];
            }
        }
        cout<<av<<endl<<aw<<endl;
        vec.clear();
    }
}

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

using namespace std;

typedef pair<unsigned long long int, int> P;

P plus_(P a, P b) {
    return P(a.first+b.first, a.second+b.second);
}

int main() {
    int w, n;
    int value[1000], weight[1000];
    P dp[2][1000];
    for (int case_num=1; true; case_num++) {
        cin >> w;
        if (w == 0) {
            return 0;
        }
        cin >> n;
        for (int i=0; i<n; i++) {
            cin >> value[i];
            cin.ignore(1);
            cin >> weight[i];
        }
        for (int i=0; i<=w; i++) {
            dp[0][i] = P(0, 0);
        }
        for (int i=1; i<=n; i++) {
            for (int j=0; j<=w; j++) {
                if (j < weight[i-1]) {
                    dp[i%2][j] = dp[(i-1)%2][j];
                }
                else {
                    P a = plus_(dp[(i-1)%2][j-weight[i-1]], P(value[i-1], -weight[i-1]));
                    P b = dp[(i-1)%2][j];
                    dp[i%2][j] = max(a, b);
                }
            }
        }
        cout << "Case " << case_num << ":" << endl;
        cout << dp[n%2][w].first << endl;
        cout << -dp[n%2][w].second << endl;
    }
}

C++: #include <string>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

int W,N;
int c[1000],w[1000];
int t[10000+10];

int main()
{
	for (int i = 1; ; i++){
		cin>>W;
		if(W == 0) break;
		cin>>N;
		for(int j =0 ; j < N; j++) scanf("%d,%d",c+j,w+j);
		printf("Case %d:\n",i);
		memset(t,-1,sizeof(t));
		t[0] = 0;
		for (int i = 0; i < N; i++){
			for (int j = W - w[i]; j >= 0; j--){
				if(t[j] == -1) continue;
				t[j+w[i]] = max(t[j+w[i]],t[j] + c[i]);
			}
		}
		int ans_id = max_element(t,t+W+1) - t;
		printf("%d\n%d\n",t[ans_id],ans_id);
	}

}

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

bool cmp(const pair<int,int> &a,const pair<int,int> &b){
	if( a.first != b.first ) return a.first < b.first;
	else return a.second > b.second;
}
int main(){
	int n,W;
	int t = 1;
	while( cin >> W >> n && W ){
		vector< pair<int,int> > cur;
		cur.push_back({0,0});
		for(int i = 0 ; i < n ; i++){
			int w,c;
			scanf("%d,%d",&c,&w);
			for(int j = 0 , t = cur.size() ; j < t ; j++ )
				cur.push_back(pair<int,int>(cur[j].first+w,cur[j].second+c));
			sort(cur.begin(),cur.end(),cmp);
			int maxi = -1;
			vector< pair<int,int> > nex;
			for(int j = 0 ; j < cur.size() ; j++){
				if( maxi >= cur[j].second ) continue;
				nex.push_back(cur[j]);
				maxi = cur[j].second;
			}cur = nex;
		}
		int ans = 0, ans2 ;
		for(int i = 0 ; i < cur.size() ; i++){
			if( cur[i].first <= W ){
				ans = cur[i].second;
				ans2 = cur[i].first;
			}
		}

		cout << "Case " << t++ << ":" << endl;
		cout << ans << endl;
		cout << ans2 << endl;
	}
}

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

using namespace std;

int N,W;

struct Treasurea
{

  int value;
  int weight;
  int flag;

  Treasurea()
  {
    value = 0;
    weight = 0;
    flag = false;
  }

};

struct Memo
{

  Treasurea record;
  bool flag;

  Memo()
  {
    record.value = 0;
    record.weight = 0;
    record.flag = false;
    flag = false;
  }

};

Memo memo[1001][1001];

Treasurea knapsack(vector<Treasurea> &treasurea, int correntWeight,int correntValue, int kind)
{

  if(correntWeight < 0)
    {
      Treasurea temp;
      temp.weight = W - (correntWeight + treasurea[kind - 1].weight);
      temp.value = correntValue - treasurea[kind - 1].value;
      return temp;
    }
  else if(memo[correntWeight][kind].flag) return memo[correntWeight][kind].record;
  else if(kind == treasurea.size())
    {
      Treasurea temp;
      temp.weight = W - correntWeight;
      temp.value = correntValue;
      return temp;
    }


  Treasurea total;

  for(int i = 0;i < treasurea.size(); ++i)
    {

      if(treasurea[i].flag) continue;

      treasurea[i].flag = true;

      Treasurea temp = knapsack(treasurea,correntWeight - treasurea[i].weight,correntValue + treasurea[i].value,i + 1);

      if(total.value < temp.value || (total.value == temp.value && total.weight > temp.weight))
        total = temp;

      treasurea[i].flag = false;

    }

  memo[correntWeight][kind].record = total;
  memo[correntWeight][kind].flag = true;

  return total;

}

int main()
{

  int case_number = 0;

  while(cin >> W && W != 0)
    {

      cin >> N;

      vector<Treasurea> treasurea(N);
      Treasurea result;

      for(int i = 0; i < N; ++i) scanf("%d,%d",&treasurea[i].value,&treasurea[i].weight);

      memset(memo,0,sizeof(memo));

      result = knapsack(treasurea,W,0,0);

      cout << "Case " << ++case_number << ":"<< endl << result.value << endl << result.weight << endl;

    }

  return 0;

}