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>
#include<string>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack> 
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
const int MAX_V=105;
int INF = 1000000000;
  
int main(){
  int n=1;
  int W,N,i,j;
  while(cin >> W ,W){
    cin >> N;
    int dp[N+1][W+1];
    rep(i,N+1){
      rep(j,W+1){
        dp[i][j]=0;
      }
    }

    rep(i,N){
      int v,w;
      char c;
      cin >> v >> c >> w;
      rep(j,W){
        dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
        if(j+w<W+1){
        dp[i+1][j+w]=max(dp[i][j]+v,dp[i+1][j+w]);
        }
      }
    }
    int value1=0;
    int weight=0;
    rep(j,W+1){
      if(dp[N][j]>value1){
        value1=dp[N][j];        
      }
    }
    rep(j,W+1){
      if(dp[N][j]==value1){
        weight=j;
        break;
      }
    }
    
    cout << "Case" << ' ' << n++ << ":" << endl;
    cout << value1 << endl;
    cout << weight << endl;  
    
  }
    return 0;
}

C++: #include <iostream>

using namespace std;

int main( void )
{
	int map[1000], save[1000];
	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);
		save[weight] = map[weight] = max(save[weight], value);
		for(int i=1; i < n; ++i) {
			scanf("%d,%d", &value, &weight);
			save[weight] = max(save[weight], value);
			for(int j=0; j < w; ++j) {
				int ww = j + weight;
				if(map[j]) {
					 if(ww < w) save[ww] = map[j] + value;
					 else		save[j] = max(save[j], map[j]);
				}
				//map[j] = save[j]; save[j] = 0;
			}
			for(int j=0; j < w; ++j) {
				map[j] = save[j]; save[j] = 0;
			}
		}
		int Max = 0, idx;
		for(int i=1; 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<cstdio>;
#include<utility>
using namespace std;



int W,N;
int w[1010],v[1010];

int dp[1010];
void init(){
	for(int i=0;i<1010;i++){
		w[i]=0;
		v[i]=0;
		dp[i]=0;
	}
}


pair<int,int> solve(){
	for(int i=0;i<N;i++){
		for(int j=1010;j--;){
			if(j-w[i]>=0){
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
			}
		}
	}
	int res=W;
	for(int i=W;i--;){
		if(dp[i]!=dp[i+1]){
			break;
		}else{
			res=i;
		}
	}
	return make_pair(dp[W],res);
}

int main(){
	int c=0;
	while(cin>>W,W!=0){
		c++;
		init();
		cin>>N;
		for(int i=0;i<N;i++){
			scanf(" %d,%d",&v[i],&w[i]);
		}
		
		
		cout<<"Case "<<c<<":"<<endl;
		pair<int,int> ans=solve();
		cout<<ans.first<<endl;
		cout<<ans.second<<endl;
	}
}

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

using namespace std;

#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,-1,sizeof(a))

int W, n;
int v[1002], w[1002];
int dp[1002][1002];

int rec(int i, int j) {
    if(dp[i][j] >= 0) return dp[i][j];

    int res = 0;
    if(i == n) {
        res = 0;
    } else if(j < w[i]) {
        res = rec(i+1, j);
    } else {
        res = max(rec(i+1,j), rec(i+1, j-w[i]) + v[i]);
    }

    return dp[i][j] = res;
}

int main() {
    for(int data = 1; ; data++) {
        ZERO(v); ZERO(w); MINUS(dp);
        scanf("%d", &W);
        if(W == 0) break;
        scanf("%d", &n);
        for(int i=0; i<n; i++) scanf("%d,%d", v+i, w+i);

        int ans = rec(0, W), wret = W;
        while(dp[n][wret] == ans) wret--;
        printf("Case %d:\n", data);
        printf("%d\n", ans);
        printf("%d\n", wret-1);
    }
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

typedef pair<int, int> obj;

int main(){
  int N, W, weight, value;
  char ch;
  int case_num = 1;

  while(1){
    cin >> W;
    if(W == 0) break;
    cin >> N;

    //printf("W = %d N = %d\n", W, N);

    vector<obj> obj_list;
    int dp[2][1010];
    memset(dp, -1, sizeof(dp));
    
    for(int i = 0; i < N; i++){
      cin >> value >> ch >> weight;
      obj_list.push_back(obj(value, weight));
      //printf("value = %d weight = %d\n", value, weight);
    }

    dp[0][0] = 0;
    dp[1][0] = 0;

    for(int i = 0; i < N; i++){
      obj o = obj_list[i];

      for(int j = 0; j <= W; j++){
        if(dp[(i+1)%2][j] != -1 && j + o.second <= W){
          dp[i%2][j+o.second] = max(dp[i%2][j+o.second], dp[(i+1)%2][j] + o.first);
        }
      }
    }
    int answer = 0;
    int answer_weight = 0;

    for(int i = 0; i <= W; i++){
      if(answer < dp[(N+1)%2][i]){
        answer = dp[(N+1)%2][i];
        answer_weight = i;
      }
      if(answer < dp[N%2][i]){
        answer = dp[N%2][i];
        answer_weight = i;
      }
    }

    cout << "Case " << case_num << ":" << endl;
    cout << answer << endl;
    cout << answer_weight << endl;

    case_num++;
  }

  return 0;
}

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

using namespace std;

const int NUM_MAX = 1001;
int dp[NUM_MAX][NUM_MAX];
int we[NUM_MAX], v[NUM_MAX];
int w, n;


void solve()
{
    int max_idx, max_value;

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

    max_idx = max_value = 0;
    for (int j = 0; j <= w; j++)
        if (max_value < dp[n][j]) {
            max_value = dp[n][j];
            max_idx = j;
        }
        
    cout << max_value << '\n' << max_idx << endl;
}

int main()
{
    int cas = 1;

    while (cin >> w, w) {
        char ch;

        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> v[i] >> ch >> we[i];

        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= w; j++)
                dp[i][j] = 0;

        cout << "Case " << cas++ << ":\n";
        solve();
    }

    return 0;
}

C++: #include <algorithm>
#include <iostream>
using namespace std;
int N,W;
int w[1000];
int c[1000];
char tmp;
int dp[1001];
int main() {
	int tc=1;
	while(cin>>W>>N){
		for(int i=0;i<N;i++){
			cin>>c[i]>>tmp>>w[i];
		}
		fill(dp+0,dp+W+1,0);
		for(int i=0;i<N;i++){
			for(int j=W;j>=0;j--){
				if(j+w[i]>W)continue;
				dp[j+w[i]]=max(dp[j+w[i]],dp[j]+c[i]);
			}
		}
		int mans=*max_element(dp,dp+W+1);
		for(int i=0;i<=W;i++){
			if(mans==dp[i]){
				cout<<"Case "<<tc++<<":"<<endl;
				cout<<mans<<endl;
				cout<<i<<endl;
				break;
			}
		}
	}
	return 0;
}