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++: 
// 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;
}

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


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;
    cout << max_value(0,wei) << endl;
    cout << max_weight(0,wei) << endl;
    cnt++;
  }
  return 0;
}

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

using namespace std;

int main(void){
  int W,n,v[1000],w[1000],dp[1001][1001],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;
    
    for(int i=W;i>=0;i--){
      if(dp[n][i] != dp[n][W]){
	cout << dp[n][W] << endl << i+1 << endl;
	break;
      }
    }
      t++;
  }

  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>

#define ll (long long)
#define REP(i,n) for(int i = 0;i<(int)n;i++)
#define FOR(i,a,b) for(int i = (a);i < (b);i++)
#define RFOR(i,a,b) for(int i = (a);i>(b);i--)

using namespace std;


int main(void){
    
    /*(x,y) = (??????,??????)*/
    int max_w;
    int number;
    int answer = 0;
    int casecounter = 1;
    while(cin >> max_w,max_w)
    {
        int dp[1002][1002] = {0};
        int w[1002] = {0},v[1002] = {0};
        cin >> number;
        for(int i  =1; i<= number;i++)
            scanf("%d%*c%d",&v[i],&w[i]);
        
        for(int j = 1; j<= number;j++)
            for(int k = 0;k<=max_w;k++)
            {
              if(j == 1 && k>=w[j])
                  dp[j][k] = v[j];
              else if(k >= w[j])
                  dp[j][k] = max(dp[j-1][k],v[j]+dp[j-1][k-w[j]]);
              else
                  dp[j][k] = dp[j-1][k];
     
                
            }
        int max = 0;
        for(int i = 1;i<=max_w;i++)
        {
            if(max < dp[number][i])
            {
                answer = i;
                max = dp[number][i];
            }
            
        }
        printf("Case %d:\n",casecounter);
        printf("%d\n",dp[number][answer]);
        printf("%d\n",answer);
        casecounter++;
    }
    return 0;
    
}

C++: #include <iostream>
using namespace std;
int main(){
	int W,N;int count=0;
	while(1){
	cin >> W ; count++;
	if(W==0) break;
	cin >> N ;
	int temp[1000][2];char ch;
	for(int i=0;i<N;i++) cin >> temp[i][0] >> ch >> temp[i][1] ;
	//全探索
	int msum_t,wsum_t;int temp_msum=0;int temp_wsum=0;
	for(int k=0;k<N;k++){
	int stack[1000]={0};int ptr=0;int msum=0;int wsum=0;
	for(int i=k;i<N;i++){
		if(wsum+temp[i][1]<=W) do{msum+=temp[i][0];wsum+=temp[i][1];stack[ptr++]=i;}while(0);
		else 
			do{for(int j=0;j<ptr;j++){
			msum_t=msum-temp[stack[j]][0]+temp[i][0];
			wsum_t=wsum-temp[stack[j]][1]+temp[i][1];
			if(msum_t>msum && wsum_t<=W) do{msum=msum_t;wsum=wsum_t;stack[j]=i;}while(0);
			else if(msum_t==msum && wsum_t<wsum) do{wsum=wsum_t;stack[j]=i;}while(0);
			};
			}while(0);
	};
	if(msum>temp_msum) do{temp_msum=msum; temp_wsum=wsum;}while(0);
	else if(msum==temp_msum && wsum<temp_wsum) temp_wsum=wsum;
	};
	cout << "Case " << count << ":\n" << temp_msum << '\n' << temp_wsum << '\n' ;
	};
}

C++: #include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	int W,n,c=1;
	while(scanf("%d%d",&W,&n),W){
		int w[n],v[n]; rep(i,n)scanf("%d,%d",v+i,w+i);
		int opt[n][W]; rep(i,n)rep(j,W)opt[i][j]=0;
		
		rep(i,n)rep(j,W){
			int a=i>0?opt[i-1][j]:0,b=i>0?opt[i-1][j-w[i]]:0;
			if(j<w[i])opt[i][j]=a;
			else opt[i][j]=max(a,v[i]+b);
		}
		int mx=0,mi;
		rep(j,W)if(opt[n-1][j]>mx)mx=opt[n-1][j],mi=j;
		printf("Case %d:\n%d\n%d\n",c++,mx,mi);
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

using db = double;
using ll = long long;
using vi = vector <int>;
#define op operator
#define pb push_back

const int N = 1e3L + 11;
int dp[N][N];

int main() {
	ios :: sync_with_stdio(0);

	int W, n;
	int _ = 0;
	while(cin >> W && W) {
		cin >> n;
		_ ++;
		memset(dp, 0, sizeof dp);
		for(int i = 1; i <= n; i ++) {
			int v, w; char c;
			cin >> v >> c >> w;
			for(int j = w; j <= W; j ++)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v);
		}
		cout << "Case " << _ << ":\n";
		cout << *max_element(dp[n], dp[n] + W + 1) << '\n';
		cout << max_element(dp[n], dp[n] + W + 1) - dp[n] << '\n';
	}

	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main(){

	int w,n,cnt=1;
	int dp[1006][1005],V[1001],W[1001];
	while(cin>>w,w){
		cin>>n;
		for(int i=0;i<n;i++)scanf("%d,%d",&V[i],&W[i]);
		int cnt=0;for(int i=0;i<n;i++)cnt+=W[i];
		if(cnt>=10000)for(;;);
		for(int i=1;i<=n;i++){
			for(int j=0;j<=w;j++){
				if(j-W[i-1]>=0)dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i-1]]+V[i-1]);
			}
		}
		int tmp=w;
		for(int i=w;i>=0;i--)if(dp[n][i]==dp[n][w])tmp=i;
		cout<<"Case "<<cnt<<":"<<endl<<dp[n][w]<<endl<<tmp<<endl;
		cnt++;
		for(int i=0;i<1001;i++)for(int j=0;j<=1000;j++)dp[i][j]=0,V[i]=W[i]=0;
	}
	return 0;
}