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<cstdio>
#include<algorithm>
using namespace std;
#define latte WORLD

struct Data{
    int v,w;
    Data(){}
    Data(int _v,int _w){
        v=_v; w=_w;
    }
    bool operator <(const Data &a)const{
        if(v==a.v) return w>a.w;
        return v<a.v;
    }
    Data operator +(const Data &a)const{
        return Data(v+a.v,w+a.w);
    }
};

int N,W;
Data t[1000],memo[1000][1001];

Data latte(int n,Data st){
    if(st.w>W) return Data(0,0);
    if(n==N) return st;
    if(memo[n][st.w].v!=-1) return memo[n][st.w];
    memo[n][st.w] = max(latte(n+1,st+t[n]),latte(n+1,st));
    return memo[n][st.w];
}

int main(){
    for(int ds=1;cin>>W,W;ds++){
        cin>>N;
        for(int i=0;i<N;i++) scanf("%d,%d",&t[i].v,&t[i].w);
        for(int i=0;i<1000;i++)for(int j=0;j<1001;j++) memo[i][j] = Data(-1,-1);
        Data ans = latte(0,Data(0,0));
        printf("Case %d:\n%d\n%d\n",ds,ans.v,ans.w);
    }
}

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

using namespace std;

int main(void){
  int W,n,v[1000],w[1000],dp[1000][1000],t=1;

  while(cin >> W,W){
    cin >> n;

    for(int i=0;i<n;i++)
    scanf("%d,%d",&v[i],&w[i]);

    for(int i=0;i<1000;i++)
      for(int j=0;j<1000;j++)
	dp[i][j]=0;
    
    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]);

    cout << "Case " << t << ":" << endl;
    cout << dp[n][W] << endl;

    int m=10000000;
    for(int j=0;j<=W;j++)
      for(int i=0;i<=n;i++)
	if(dp[n][W]==dp[i][j]){
	  m=min(m,j);
	}
    cout << m << endl;
    t++;
  }

  return 0;
}

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


int c;
vector<int> v;
vector<int> w;
void init(){
  c= 0;
  v.clear();
  w.clear();
}


bool input(){
  cin>>c;
  if(c==0)return false;
  int a;
  cin>>a;
  v.resize(a);
  w.resize(a);
  for(int i=0;i<a;i++){
    char tmp;
    cin>>v[i]>>tmp>>w[i];
  }
  return true;
}


vector<int> solve(){
  vector<int> ans(2);
  ans[0] = 1;
  ans[1] = 2;
  vector<vector<int>> dp(1100,vector<int>(1100,0));
  for(int i=0;i<c+10;i++){
    if(w[0]<=i){
      dp[0][i] = v[0];
    }
  }
  for(int i=1;i<v.size();i++){
    for(int j=0;j<c+10;j++){
      dp[i][j] = dp[i-1][j];
      if(w[i]<=j) dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
    }
  }
  ans[0] = dp[v.size()-1][c];
  for(int i=c;i>0;i--){
    if(dp[v.size()-1][i]==dp[v.size()-1][i-1])continue;
    else{
      ans[1] = i;
      return ans;
    }
  }
  ans[1] = 0;
  return ans;
}

int main(){
  int case_n = 0;
  while(init(),input()){
    case_n++;
    auto ans = solve();
    cout<<"Case "<<case_n<<":"<<endl;
    cout<<ans[0]<<endl;
    cout<<ans[1]<<endl;
  }
}

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

using namespace std;

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

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<bits/stdc++.h>
using namespace std;
/* 変数名を被らせない
   デバッグコードを取り除く */
#define ANSWER(x) cout<<x<<endl
#define debug(x) cout<<#x<<": "<<x
const int MAX_INT = 1000000;
int n,w,ans,cnt=1;
int value[1001],weight[1001],dp[1001][1001];;
int solve(int a,int b);
int main(){
  while(1){
    memset(dp,-1,sizeof(dp));
    cin >> w;
    if(w==0)break;
    cin >> n;
    for(int i=0;i<n;i++){
      scanf("%d,%d",&value[i],&weight[i]);
    }
    ans = solve(0,w);
    for(int i=0;i<=w;i++){
      if(solve(0,i) == ans){
	cout <<"Case " << cnt <<':' << endl <<  ans <<endl << i << endl;
	break;
      }
    }
    cnt++;
  }
}
int solve(int a,int b){
  if(dp[a][b] != -1)return dp[a][b];
  if(a == n)return 0;
    
  else if(b < weight[a])return dp[a][b] = solve(a+1,b);
  else return dp[a][b] = max(solve(a+1,b-weight[a])+value[a],solve(a+1,b));
}

C++: 
// dpの練習
// dpでなく、愚直に組んだプログラミング
// ナップサック問題とほぼ同じ

#include <iostream>
#include <algorithm>

using namespace std;

int wei; // 持てる最大の重さ
int n; // お宝の数
int v[1001]; // お宝の価値
int w[1001]; // お宝の重さ
 // グローバル配列は0で初期化されている

int max_value(int i, int j) {
  int value;
 
  if (i == n) {
    // 品物がもう残っていないときは、価値の和の最大値は0で確定
    //もうお宝がないつまり、価値は0
    value = 0;
  } else if (j < w[i]) {
    //風呂敷が持てる重さを超えてしまう
    // 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理
    // i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする
    value = max_value(i + 1, j);
  } else {
    //左がお宝を入れない、右がお宝を入れた場合
    // 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ
    value = max( max_value(i + 1, j), max_value(i + 1, j - w[i]) + v[i] );
  } 
  return value;
}

void max_weight( int ans ){

  int w_min;
   
  for (int i = wei -1 ; i >= 0 ; i--){
    if( ans != max_value( 0 , i ) ){
         w_min = i + 1;
         break;
    }
  }
  cout << w_min << endl;  
}


int main(void){

  int cnt = 1;
  while( cin >> wei ){
    if( wei == 0 )break;
    cin >> n;
    char ten;
    for( int i = 0 ; i < n ; i++ ){
      cin >> v[i] >> ten >> w[i];
    }
    cout << "Case " << cnt << ":" << endl;
    int ans = max_value( 0 , wei );
    cout << ans << endl;
    max_weight(ans);
    cnt++;
  }
  return 0;
}

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

int main(){
	const int nmax = 1000;
	char c;
	int count = 1;
	int dp[nmax+1];
	int n, w;
	int val[nmax+1], weight[nmax+1];
	while(cin >> w){
		if(w == 0) break;
		cin >> n;
		for(int i = 1; i <= n; i++){
			cin >> val[i] >> c >> weight[i];
		}
		for(int i = 0;i <= w; i++) dp[i] = 0;
		for(int i = 1; i <= n; i++){
			for(int j = w; j >= weight[i]; j--){
				dp[j] = max(dp[j],dp[j - weight[i]] + val[i]);
			}
		}
		cout << "Case " << count++ << ":" << endl;
		cout << dp[w] << endl;
		while(w > 0 && dp[w] == dp[w-1]) w--;
		cout << w << endl;
	}
	return 0;
}