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++: const int MAX_N = 1000; // n????????§???
const int MAX_W = 5000; // W????????§???

// ??\???
int n, W;
int w[MAX_N], v[MAX_N];

// ?????¢??????????????????
// dp[i][j]???i????????\?????????????????????????????????j??\?????????????????????????????¨??????????????????????????§????????¨??????
// -1????????????????±??????§???????????¨?????¨???
int dp[MAX_N + 1][MAX_W + 1];

// i????????\?????????????????????????????????j??\?????????????????????????????¨?????????
// ???????????????????????????????????§??????????????¢??°
int rec_dp(int i, int j) {
  if (dp[i][j] != -1) {
    // ?????§?????????????????¨??????????????????????????????????????¨
    return dp[i][j];
  }
  int res;
  if (i == n) {
    // ????????????????????£??????????????¨?????????????????????????????§??????0??§?¢????
    res = 0;
  } else if (j < w[i]) {
    // ???????????????????¶?????????????i?????\????????????????????§?????\?????????????????????????????????
    res = rec_dp(i + 1, j);
  } else {
    // ??????i?????\???????????\??????????????????????????§???????????????????????????????????§?????????????????¶
    res = max(
        rec_dp(i + 1, j),
        rec_dp(i + 1, j - w[i]) + v[i]
    );
  }
  // ?????????????????????????¨???¶??????
  return dp[i][j] = res;
}

void solve_dp() {
  memset(dp, -1, sizeof(dp)); // ?????¢??????????????????-1??§??????????????\??????for???????????¨??????
//  for (int i = 0; i < MAX_N + 1; i++)
//    for (int j = 0; j < MAX_W + 1; j++)
//      dp[i][j] = -1;
  
  // 0????????\?????§??????W??\????????´?????????????????¨?????????
  cout << rec_dp(0, W) << endl;
}

C++: #include<bits/stdc++.h>

using namespace std;

int N, W, w[1001], v[1001];
const int MAX_W=1000, MAX_N=1000;
int dp[MAX_W+1][MAX_N+1];

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

int main(){
	int q = 1, ans;
	string in;
	while(1){
		cin >> W;
		if(!W) break;
		cin >> N;
		for(int i=0;i<=N;i++){
			w[i]=0;
			v[i]=0;
			for(int j=0;j<=W;j++){
				dp[i][j] = 0;
			}
		}
		for(int i=0;i<N;i++){
			cin >> in;
			int flag=0;
			for(int j=0;j<in.size();j++){
				if(in[j]==',') flag++;
				else if(flag==1) w[i] = w[i]*10 + (in[j] - '0');
				else v[i] = v[i]*10 + (in[j] - '0');
			}
			//cout << w[i] << " " << v[i] << endl;
		}
		solve();
		for(int j=0;j<=W;j++){
			if(dp[0][j]==dp[0][W]){
				//cout << "hoge:" << j << endl;
				ans = j;
				break;
			}
		}
		cout << "Case " << q << ":" << endl;
		cout << dp[0][W] << endl << ans << endl;
		q++;
	}
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>
#include<tuple>
#include<stack>


using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpl;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };

#define ARRAY_MAX 1005

const int INF = 1 << 30;
const int MOD = 1e9 + 7;

int dp[ARRAY_MAX][ARRAY_MAX];//dp[i][j]:=i番目までを見た時に重さとなる時の最大価値

int main() {

	int W;
	int cnt = 1;
	while (cin >> W, W)
	{
		int n;
		char c;
		cin >> n;
		vector<int> v(n), w(n);
		for (int i = 0; i < n; i++)
		{
			cin >> v[i] >> c >> w[i];
		}

		for (int i = 0; i < ARRAY_MAX; i++)
		{
			for (int j = 0; j < ARRAY_MAX; j++)
			{
				dp[i][j] = 0;
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= W; j++) {
				if (j + w[i] > W) {
					//重さを上限を超える場合は入れられない
					dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
				}
				else {
					//入れられる場合
					dp[i + 1][j + w[i]] = max(dp[i+1][j + w[i]], dp[i][j] + v[i]);//入れる場合
					dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);//入れない場合
				}	
			}
		}
		int ans_w = 0;
		int ans_v = 0;

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

			if (ans_v < dp[n][i])
			{
				ans_v = dp[n][i];
				ans_w = i;
			}
		}
		cout << "Case " << cnt << ":" << endl;
		cout << ans_v << endl << ans_w << endl;
		cnt++;
		v.shrink_to_fit();
		w.shrink_to_fit();
	}
}

C++: #include<cstdio>

int main(){
	int w,n,count=1;
	scanf("%d",&w);
	while(w){
		scanf("%d", &n);
		int a[n][2];
		for(int i = 0; i < n; i++){
			scanf("%d,%d", &a[i][0], &a[i][1]);
		}
		unsigned long long c = 1 << n,b;
		int max = 0,weight, weightm = 0,sum;
		while(c){
			sum = 0;
			weight = 0;
			b = 1;
			for(int i = 0; i < n; i++){
				if(c & b){
					sum += a[i][0];
					weight += a[i][1];
				}
				if(weight > w){
					break;
				}
				if(sum > max){
					max = sum;
					weightm = weight;
				}
				if(sum == max && weight < weightm){
					weightm = weight;
				}
				b = b << 1;
			}
			c--;
		}
		printf("Case %d:\n%d\n%d\n", count++, max, weightm);
		scanf("%d", &w);
	}

}

C++: #include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int W, N, value, weight, num = 1;
int v[1000], w[1000];
int dp[1000][1000]; //[n][w]
	
int main(){
	while(true){
		scanf("%d", &W);
		if(W == 0) break;
		scanf("%d", &N);
		for(int i = 0; i < N; i++){
			scanf("%d,%d", &v[i], & w[i]);
		}
		
		for(int j = 0; j < W; j++){
			dp[N][j] = 0;
		}
		
		for(int i = N - 1; i >= 0; i--){
			for(int j = 0; j < W; j++){
				if(j < w[i]) dp[i][j] = dp[i + 1][j];
				else dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
			}
		}
		/*for(int i = 0; i < N; i++){
				cout << v[i] << " " << w[i] << endl;
		}
		for(int i = 0; i <= N; i++){
			for(int j = 0; j < 109; j++){
				cout << dp[i][j] << " " ;
			}
			cout << endl;
		}*/
		value = 0;
		weight = 0;
		for(int j = 0; j < W; j++){
			if(value < dp[0][j]){
				value = dp[0][j];
				weight = j;
			}
		}
		cout << "Case " << num << ":" << endl;
		cout << value << endl << weight << endl;
		num++;
	}
	return 0;
}