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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
int dp[1111][1111];
int w[1111],v[1111];
int main(){
  int W,N;
  int c = 1;
  while(1){
    cin >> W;
    if(!W)break;
    cin >> N;
    for(int i=0;i<N;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    memset( dp , 0 , sizeof(dp) );
    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] );
	}
      }
    }
    int ret=0,value=0;
    for(int i=0;i<=W;i++){
      if(value<dp[N][i]){
	ret = i;
	value = dp[N][i];
      }
    }
    cout << "Case " << c++ << ":" <<  endl;
    cout << dp[N][W] << endl;
    cout << ret << endl;
  }
}

C++: #include<iostream>
#include<algorithm>
#define MAX_N 1001
#define MAX_W 1001
using namespace std;


int dp[MAX_N][MAX_W];
int n,W;
int w[MAX_N];
int v[MAX_N];

void solve(){
  memset(dp,0,sizeof(dp));
  cout<<"Case 1:"<<endl;
  for(int i=0;i<n;i++){
    for(int j=0;j<=W;j++){
      if(j>=w[i]){
	dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
      }else{
	dp[i+1][j]=dp[i][j];
      }
    }
  }
  cout << dp[n][W] << endl;
  int tmp=0;
  int weight;
  for(int i=0;i<=W;i++){
    if(dp[n][i]>tmp){
      tmp=dp[n][i];
      weight=i;
    }
  }
cout << weight << endl;
}

int main(){
  while(cin>>W,W){
    cin>>n;
    for(int i=0;i<n;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    solve();
  }

  return 0;
}

C++: #include <iostream>

int solve (int);

int main(int argc, char const* argv[])
{
    int times = 0;

    while (true) {
        if(solve(++times) == 1) break;
    }
    return 0;
}

int solve(int times) {
    int max_weight, item_count;
    int prices[1000] = {0};
    int weights[1000] = {0};

    std::cin >> max_weight;
    if (max_weight == 0) return 1;

    std::cin >> item_count;

    for(int i = 0; i < item_count; i++) {
        int p, w;
        char c;
        std::cin >> p >> c >> w;

        prices[i]  = p;
        weights[i] = w;
    }

    int dp[1010] = {0};


    for (int i = 0; i < item_count; i++) {
        if (dp[weights[i]] == 0) {
            dp[weights[i]] = prices[i];
        } else {
            dp[weights[i]] = std::max(dp[weights[i]], prices[i]);
        }

        for (int j = 1; j < 1001; j++) {
            if (dp[j] == 0) continue;
            if (j == weights[i]) continue;

            int plus_weight = j + weights[i];
            int plus_price  = dp[j] + prices[i];
            if (plus_weight >= max_weight) continue;
            if (plus_weight >= 1001) continue;
            dp[plus_weight] = std::max(dp[plus_weight], plus_price);
        }
    }

    int min_weight = 99999;
    int max_price  = 0;
    for (int i = 0; i < max_weight; i++) {
        if (max_price < dp[i]) {
            max_price  = dp[i];
            min_weight = i;
        } else if (max_price == dp[i]) {
            min_weight = std::min(i, min_weight);
        }
    }

    std::cout << "Case " << times << ":" << std::endl;
    std::cout << max_price << std::endl;
    std::cout << min_weight << std::endl;

    return 0;
}

C++: #include <iostream>
#include <array>
#include <string>
#include <tuple>
#include <vector>
#include<stdio.h>
#include<string.h>
using namespace std;
//using ll = long long;
#define out(s) cout << (s) << endl;

int dp[1001][1001];

int main()
{
	int W, N, cnt = 1;
	cin >> W;
	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]);
					dp[i + 1][n + wi] = max(dp[i][n] + vi, dp[i][n]);
				}
			}
		}
		int dp_max = dp[N][W];
		int index = W;
		for (size_t i = W; i > 0; i--)
		{
			if (dp_max == dp[N][i])index = i;
		}
		cout << "Case " << cnt << ":" << endl << dp_max << endl << index << endl;
		cin >> W;
		cnt++;
	}
	return 0;
}

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

using namespace std;

const int MAX_N = 1002;
const int MAX_W = 10001;
const int MAX_V = 10001;

int dp[MAX_N][MAX_W];
int w[MAX_N];
int v[MAX_N];

int N,W;

int main(){
  int c = 1;
  while(cin >> W , W){
    cin >> N;
    for(int i=0; i<N; i++){
      scanf("%d,%d", &v[i], &w[i]);
    }
    memset(dp,0,sizeof(dp));

    for(int i=0; i<N; i++){
      for(int j=0; j<=W; j++){
        if(j >= w[i]){
          dp[i+1][j] = max(dp[i][j] , dp[i][j-w[i]]+v[i]);
        }
        else dp[i+1][j] = dp[i][j];
      }
    }
    
    int weight=1000000;
    for(int i=0; i<=N; i++){
      for(int j=0; j<=W; j++){
        if(dp[i][j] == dp[N][W]){
          weight = min(weight,j);
        }
      }
    }
  out:;
    printf("Case %d:\n%d\n%d\n", c++, dp[N][W], weight);
  }

  return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){

	int cnt, N, W, value, weight, v[1000][1001], w[1000][1001];

	cnt = 0;

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

		for(int i=0; i<N; i++){
			for(int j=0; j<W; j++){
				v[i][j] = 0;
				w[i][j] = 0;
			}
		}
				
		for(int i=1; i<=N; i++){
			scanf("%d, %d", &value, &weight);
			for(int j=0; j<=W; j++){
				for(int k=0; k<=j; k++){
					if(w[i-1][k] + weight < W && v[i-1][k] + value > v[i][j]){
						v[i][j] = v[i-1][k] + value;
						w[i][j] = w[i-1][k] + weight;
					}
				}
			}
		}

		cout << "Case " << cnt << ":" << endl;
		cout << v[N][W] << endl;
		cout << w[N][W] << endl; 
		
	}

	return 0;

}

C++: #include<stdio.h>
#include<string.h>
#include<math.h>
int a,s,d[1001],f[1001],g[1001][1001],h,i,j,z,x=1;
int main(void)
{
	while(1){
		scanf("%d",&a);
		if(a==0)	break;
		scanf("%d",&s);
		for(i=0;i<s;i++)
			scanf("%d,%d",&d[i],&f[i]);
		for(i=0;i<s;i++){
			for(j=0;j<a;j++)
				g[i][j]=-1;
		}
		g[0][0]=0;
		for(i=0;i<s;i++){
			for(j=0;j<=a;j++){
				if(g[i][j]!=-1){
					if(g[i][j]>g[i+1][j])
						g[i+1][j]=g[i][j];
					if(j+f[i]<=a){
						if(g[i][j]+d[i]>g[i+1][j+f[i]])
							g[i+1][j+f[i]]=g[i][j]+d[i];
					}
				}
			}
		}
		h=0;
		for(i=0;i<=a;i++){
			if(h<g[s][i]){
				h=g[s][i];
				z=i;
			}
		}
		printf("Case %d:\n",x);
		printf("%d\n%d\n",h,z);
		x++;
	}
	return 0;
}