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 <stdio.h>
#include <vector>
#include <algorithm>

#define TEST 1
typedef std::pair<int,int> pi;

struct Pred
{
    bool operator()(const pi& f,const pi& s)//<
    {
        return f.second > s.second;
    }
};
pi rec_check(const std::vector<pi> &data,int start,int remw)
{
    if(start >=data.size() )
        return pi(0,0);
    if(data[start].second > remw)
        return rec_check(data,start+1,remw);
    pi div0= rec_check(data,start + 1,remw - data[start].second);
    div0.first+=data[start].first;
    div0.second+=data[start].second;
    pi div1 = rec_check(data,start + 1,remw);
    if(div0.first > div1.first )
        return div0;
    if(div0.first < div1.first)
        return div1;
    if(div0.second <div1.second)
        return div0;
    return div1;
    
}
int main(void)
{
    int ccount=1;
    int w,n;
    using namespace std;
    vector<pair<int,int> > data;
    while(scanf("%d%d",&w,&n)==2 && w!=0)
    {
        data.assign(n,std::pair<int,int>(0,0));
        for(int i=0;i<n;i++)
        {
            scanf("%d%*[,]%d",&data[i].first ,&data[i].second );
        }
        Pred pred;
        sort(data.begin(),data.end(),pred);
        printf("Case %d:",ccount);
#if TEST
        for(int i=0;i<n;i++)
        {
            printf("val=%d,wei=%d\n",data[i].first,data[i].second);
        }
#endif
        pi result=rec_check(data,0,w);
        printf("%d\n%d\n",result.first,result.second);
        data.clear();
        ccount++;
    }
    return 0;
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()

const int MAXW = 1000, MAXN = 1000;

int dp[MAXN + 1][MAXW + 1];
int w[MAXN + 1];
int v[MAXN + 1];

int main()
{
    int wl, n, casen = 1;
    char t;
    while(cin >> wl && wl)
    {
        cin >> n; REP(n) cin >> v[i] >> t >> w[i];

        memset(dp, 0, sizeof(dp));
        
        REP(n)rep(j, wl+1 - w[i])
            dp[i+1][j + w[i]] = max(dp[i][j + w[i]], dp[i][j] + v[i]);
        
        int answ = 0, ansv = 0;
        REP(wl+1)if(ansv < dp[n][i]){ ansv = dp[n][i]; answ = i;}
        cout << "Case " << casen << ":\n" << ansv << "\n" << answ << endl;
        casen++;
    }

    return 0;
}

C++: #include<iostream>
using namespace std;
int main(){
  int dp[1001][1001];
  int n,W;
  int v[1000],w[1000];
  int num=0;
  while(cin>> W,W){
    num++;
    cin>> n;
    for(int i=0;i<w+1;i++){
      dp[0][i]=0;
    }

    for(int i=0;i<n;i++){
      char c;
      cin>> v[i]>> c>> w[i];
    }

    for(int i=1;i<=n;i++){
      for(int j=1;j<=W;j++){
	if(j<w[i-1]){
	  dp[i][j]=dp[i-1][j];
	}else{
	  dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
	}
      }
    }

    int mv=0,mw;
    for(int j=0;j<=W;j++){
      if(mv<dp[n][j]){
	mv=dp[n][j];
	mw=j;
      }
    }
    /*for(int i=0;i<=n;i++){
      for(int j=0;j<=W;j++){
	cout<< dp[i][j];
      }
      cout<< endl<< endl;
    }
    */
    cout<< "Case "<< num<< ":"<< endl;
    cout<< mv<< endl;
    cout<< mw<< endl;
  }
}

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

using namespace std;

int w[1001];
int v[1001];

int dp[1001][10001];

int W,N;

int solve(){
    memset(dp, 0, sizeof(dp));
    for(int i=0; i<N; i++){
        for(int j=0; j<=W; j++){
            if(j - w[i] > 0){
                dp[i+1][j] = max(dp[i][j] , dp[i][j-w[i]] + v[i]);
            }else{
                dp[i+1][j] = dp[i][j];
            }
        }
    }
    return dp[N][W];
}

int main(){
    int t=1;
    while(cin >> W, W){
        cin >> N;
        for(int i=0; i<N; i++){
            scanf("%d,%d",&v[i],&w[i]);
        }
        cout << "Case " << t++ << ":" << endl;
        cout << solve() << endl;

        int i = N, j = W;
        int wei = 0;
        while(i != 0){
            for(int l = 0; l*w[i-1] <= j; l++){
                int take = dp[i-1][j - l*w[i-1]] + l*v[i-1];
                if(take == dp[i][j]){
                    wei += l*w[i-1];
                    j -= l*w[i-1];
                    i--;
                    break;
                }
            }
        }
        cout << wei << endl;
    }
}

C++: #include <iostream>
#include <vector>
#include <algorithm>   
using namespace std;   
  
int main(){   
       
    int l, v, w, N, W, maxv, num = 1;   
    char c;   
       
    while(cin >> W){   
        if(W == 0) break;   
        cin >> N;   
        vector<int> A(W + 1);   
        A[0] = 0;   
        for(int i = 1; i <= W; i++) A[i] = -1;   
        for(int j = 0; j < N; j++){   
            cin >> v >> c >> w;   
            for(int k = W; k >= 0; k--){   
                if(A[k] > -1 && k+w <= W){   
                    A[k+w] = max(A[k+w], A[k]+v);   
                }   
            }   
        }   
           
        maxv = 0;   
        for(l = 0; l <= W; l++) maxv = max(maxv, A[l]);   
        for(l = 0; l <= W; l++) if(A[l] == maxv) break;   
           
        cout << "Case " << num << ":" << endl;   
        cout << maxv << endl << l << endl;   
        num++;   
    }   
       
    return 0;   
}