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<stdio.h>
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <functional>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <string>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <queue>
#include<iomanip>
#include<bitset>
#include<stack>
#include<set>
#include<limits>
#include <complex>
#include<cstdlib>
using namespace std;
vector<long long int> divisor(long long int n) {
	vector<long long int> res;
	for (long long int i = 1; i * i <= n; ++i) {
		if (n % i == 0) {
			res.push_back(i);
			if (i * i != n) res.push_back(n / i);
		}
	}
	sort(begin(res), end(res));
	return res;
}

int main() {
	int a = 1;
	while (1) {

		int W; cin >> W;

		if (W) {
			int N; cin >> N;
			vector<int>vs, ws;
			for (int i = 0; i < N; ++i) {
				string st; cin >> st;
				auto it = st.find(',');
				int a = stoi(st.substr(0, it));
				int b = stoi(st.substr(it + 1, st.size() - it - 1));
				vs.push_back(a);
				ws.push_back(b);
			}
			vector<vector<int>>dp(N + 1, vector<int>(W + 1,0));
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j <= W; ++j) {
					if (j + ws[i] <= W) {
						dp[i + 1][j + ws[i]] = max(dp[i + 1][j + ws[i]], dp[i][j] + vs[i]);
					}
					dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
				}
			}
			int amax = -1;
			int amin = 999999;
			for (int i = 0; i <= W; ++i) {
				amax = max(amax, dp[N][i]);
			}
			for (int i = 0; i <= W; ++i) {
				if (dp[N][i] == amax) {
					amin = i; break;
				}
			}
			cout << "Case " << a << ":" << endl;
			cout << amax << endl;
			cout << amin << endl;
			a++;
		}
		else {
			break;
		}
	}





	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
	int W,N;
	int C=0;
	while(cin>>W){
		if(!W)break;
		cin>>N;
		int v[1000],w[1000],SUMW;
		for(int i=0;i<N;++i) scanf("%d,%d",&v[i],&w[i]);
		short DP[1001][1001];
		for(int i=0;i<=N;++i) DP[0][i]=0;
		for(int i=1;i<=N;++i){
			for(int j=0;j<=W;++j){
				if(w[i]>j){//入らない時
					DP[i][j]=DP[i-1][j];
				}else{//入る時
					DP[i][j]=max((int)(DP[i-1][j]),(int)(DP[i-1][j-w[i]]+v[i]));
				}
			}
		}
		SUMW=W;
		for(int j=W;j>=1;--j) for(int i=N;i>=1;--i) if(DP[N][W]==DP[i][j])SUMW=j;
		cout<<"case "<<++C<<":\n";
		cout<<DP[N][W]<<"\n"<<SUMW<<"\n";
	}
	return 0;
}

C++: #include<iostream>
using namespace std;
int max(int n,int m){
  return(n>m?n:m);
}
int main(){
  int nap; //重さ
  int n;//お宝の数
  int c = 1;
  int ans = 0;
  int ans2 = 0;
  int mv = 0; //最大の重さ
  int cach; //価値の合計
  while(cin>>nap){
    if(nap==0) break;
    cin >> n;
  int so[nap+1]; //総数
  int kach[n]; //価値
  int val[n]; //重さ
  char a;
  for(int i=1;i<=nap;i++){ 
    so[i] = -1;
    so[0] = 0;
  }
  for(int i=0;i<n;i++){
    cin >> kach[i] >> a >> val[i];
    mv = nap - val[i];
    for(int j=mv;j>=0;j--){
      if(so[j]!=-1){
	cout << j << endl;
	cach = kach[i] + so[j];
	so[val[i]+j] = max(so[val[i]+j],cach);
      }
    }
  }
  for(int i=0;i<=nap;i++){
    if(ans<so[i]){
      ans = so[i];
      ans2 = i;
    }
}    
  cout << "Case " << c++ << ':' << endl;
  cout << ans << endl << ans2 << endl;
  ans = 0;
  ans2 = 0;
}
  return 0;
}

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("Case %d:\n%d\n%d\n",cnt,max_y,max_g);
    cnt++;
  }
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[1001][1001],wait[1001],value[1001];
void Initialization()
{
    for(int i=0;i<1001;i++)for(int j=0;j<1001;j++)dp[i][j]=-1;
}
int power(int n)
{
    int num=1;
    for(int i=1;i<=n;i++)num*=10;
    return num;
}
int serch(int i,int j,int n)
{
    int num;
    if(dp[i][j]>-1)return dp[i][j];
    else if(i==n)num=0;
    else if(j<wait[i])num=serch(i+1,j,n);
    else num=max(serch(i+1,j,n),serch(i+1,j-wait[i],n)+value[i]);
    return dp[i][j]=num;
}
int waitserch(int n,int w,int num)
{
    int wai=w,co=0;
    for(int i=n;i>0;i--){
        for(int j=1;j<w;j++){
                if(dp[i][j]==0&&wai>j){
                        co++;
                        wai=j;
                }
        }
    }
    if(co==0)wai=0;
    return w-wai;
}
int main()
{
    int n,w,point,num=1,wai=0;
    string str;
    while(cin>>w&&w!=0){
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>str;
            value[i]=0;wait[i]=0;
            for(int j=0;;j++){
                if(str[j]==','){
                    for(int k=0;k<j;k++)value[i]+=power(j-k-1)*(str[k]-'0');
                    point=j;
                }
                if(str[j]=='\0'){
                    for(int k=point+1;k<j;k++)wait[i]+=power(j-k-1)*(str[k]-'0');
                    break;
                }
            }
        }
        Initialization();
        point=serch(0,w,n);
        wai=waitserch(n,w,point);
        cout<<"Case "<<num<<":\n"<<point<<endl<<wai<<endl;
        num++;
    }
}