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 <algorithm>

using namespace std;

int W, N, casenum = 0, ans, wmin;
int v[1000], w[1000];
int dp[1001][1001];

int rec_dp(int, int);
void solve();

int main(){
	int i;
	char c;
		
	while(1){
		cin >> W >> N;
		if(W == 0)
			break;
		
		casenum++;
		for(i = 0; i < N; i++)
			cin >> v[i] >> c >> w[i];
		
		memset(dp, -1, sizeof(dp));
		ans = rec_dp(0, W);
		
		for(i = 0; i < W; i++){
			if(rec_dp(0, i) == ans){
				wmin = i;
				break;
			}
		}
		
		solve();
	}
	
	return 0;
}

int rec_dp(int i, int j){
	if(dp[i][j] != -1)
		return dp[i][j];
	
	int res;
	
	if(i == N)
		res = 0;
	else if(j < w[i])
		res = rec_dp(i + 1, j);
	else
		res = max(rec_dp(i + 1, j), rec_dp(i + 1, j - w[i]) + v[i]);
	
	return dp[i][j] = res;
}

void solve(){
	cout << "Case" << " " << casenum << ":" << endl;
	cout << ans << endl;
	cout << wmin << endl;
}

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

typedef struct{
  int g;
  int ye;
}SET;

int main(){
  
  int n,w;
  int cnt=1;
  while(1){
    
    scanf("%d",&w);
    if(w==0)break;
    scanf("%d",&n);
    SET data[1111]={0}; 
    int memo[1111][1111]={{0}};
    int max_y=0;
    int max_g=1111;
    
    for(int i=0;i<n;i++){
      scanf("%d,%d",&data[i].ye,&data[i].g);
    }
    memo[0][data[0].g]=data[0].ye;
    for(int i=1;i<n;i++){
      if(data[i].ye>memo[i-1][data[i].g]){
	memo[i][data[i].g]=data[i].ye;
      }
      for(int j=1;j<=w;j++){
	if(memo[i-1][j]>0){
	  if(memo[i-1][j]>memo[i][j]){
	    memo[i][j]=memo[i-1][j];
	  }
	  if(j+data[i].g<=w){
	    memo[i][j+data[i].g]=memo[i-1][j]+data[i].ye;
	  }
	}
	if(max_y<=memo[i][j]){
	  if(max_y==memo[i][j]){
	    if(max_g>j){
	      max_g=j;
	    }
	  }
	  else{
	    max_g=j;
	    max_y=memo[i][j];
	  }
	  printf("%d %d ",max_g,max_y);
	}
      }    
    }
    printf("\n");
    for(int i=0;i<n;i++){
      for(int j=0;j<=w;j++){
	printf("%4d",memo[i][j]);
      }
      printf("\n");
    }
    printf("Case %d:\n%d\n%d\n",cnt,max_y,max_g);
    cnt++;
  }
}

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

const int MAX_W = 1000+1;
const int MAX_N = 10000+1;

int dp[MAX_N][MAX_W]; // dp[i][j]: 重さj以下でi~n-1の宝を使った時の最大の価値
int weight[MAX_N];
int value[MAX_N];
int n, w;
int ans_v, ans_w; // 答え

void solve() {
  ans_v = ans_w = -1;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= w; j++)
      dp[i][j] = -1;
  
  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 >= weight[i])
        dp[i][j] = max(
            dp[i+1][j],
            dp[i+1][j-weight[i]] + value[i]);
      else
          dp[i][j] = dp[i+1][j];

      if (ans_v < dp[i][j] || ans_v <= dp[i][j] && j < ans_w) {
        // 最小の重さを記録しておく
        ans_v = dp[i][j];
        ans_w = j;
      }
    }
  }
}

int main() {
  int case_num = 0;

  while(cin >> w, w != 0) {
    cin >> n;
    for (int i = 0; i < n; i++) {
      char c; // カンマは読み捨てる
      cin >> value[i] >> c >> weight[i];
    }
    solve();
    case_num++;
    cout << "Case " << case_num << ":" << endl;
    cout << ans_v << endl << ans_w << endl;
  }
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(2e5 + 5);
const double EPS = 1e-11;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

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

int main() {
    int cnt=1;
    string tmp;
    while(cin >> W,W){
        cin >> n;
        REP(i,n){
            scanf("%d,%d",&v[i],&w[i]);
        }
        REP(i,n+1)fill(dp[i],dp[i]+1005,0);
        REP(i,n){
            REP(j,W+1){
                if(j>=w[i]) dp[i+1][j] = max(dp[i+1][j],dp[i][j-w[i]]+v[i]);
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            }
        }
        int wmin = W;
        REPR(i,W){
            if(dp[n][i]!=dp[n][W])break;
            wmin = i;
        }
        cout << "Case " << cnt << ":" << endl;
        cout << dp[n][W] << endl;
        cout << wmin << endl;
        cnt++;
    }
    return 0;
}

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

int main() {
	int setID = 0;
	while (true) {
		int W, N;
		if(!(cin>>W>>N)) break;
		cout << "Case " << ++setID  << ':' << endl;
		vector<int> v(N), w(N);
		for (auto i = 0; i < N; i++)
			scanf("%d,%d", &v[i], &w[i]);
		vector<vector<int>> dp(N+1, vector<int>(W+1, 0));
		for (auto i = N-1; i >= 0; i--) {
			for (auto j = W; j >= 0; j--) {
				dp[i][j] = j < w[i]
					? dp[i+1][j]
					: max(dp[i+1][j], dp[i+1][j-w[i]]+v[i]);
			}
		}
		int weight;
		for (weight = W; weight >= 0; weight--)
			if (dp[0][weight] != dp[0][W]) break;
		cout << dp[0][W] << endl << ++weight << endl;
	}
	return 0;
}

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

int a[1000] = { 0 };
int b[1000] = { 0 };
int w, n, mv, mw;
void solve(int W, int f, int sum) {
	f = min(f, n) + 1;
	for (int i = f; i < n; i++) {
		if (W - b[i] < 0) {
			mw = max(w - W, mw);
			if (sum == mv) mw = min(w - W, mw);
			mv = max(sum, mv);
			continue;
		}
		solve(W - b[i], f, sum + a[i]);
	}
}

int main() {
	int u = 0;
	while (scanf("%d", &w)) {
		if (w == 0) break;
		scanf("%d", &n);

		mv = 0;
		mw = w;
		u++;
		for (int i = 0; i < n; i++) {
			scanf("%d,%d", &a[i], &b[i]);
		}

		solve(w, -1, 0);
		printf("Case %d:\n%d\n%d\n", u, mv, mw);
	}
	return 0;
}

C++: #include <iostream>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
	int weight;
	int n,v,w,c=0;
	int dp[1001][1001];
	while(scanf("%d\n",&weight) && weight){
		c++;
		rep(i,1001)rep(j,1001)dp[i][j]=0;
		
		scanf("%d\n",&n);
		for(int k=1;k<=n;k++){
			scanf("%d,%d\n",&v,&w);
			for(int i=w;i<=weight;i++){
				dp[k][i] = max(dp[k-1][i],dp[k-1][i-w]+v);
			}
		}
		printf("Case %d:\n",c);
		printf("%d\n",dp[n][weight]);
		for(int i=0;i<=weight;i++){
			if(dp[n][i]==dp[n][weight]){
				printf("%d\n",i);
				break;
			}
		}
	}
}