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 <vector>
#include <array>
#include <map>
#include <algorithm>
typedef unsigned LL;

typedef struct tuple{
    LL weight;
    LL value;
} tuple;

bool operator<(const tuple& t1, const tuple& t2){ return t1.value < t2.value; }
bool operator==(const tuple& t1, const tuple& t2){ return t1.value == t2.value; }
tuple operator+(const tuple& t1, const tuple& t2){ return tuple {t1.weight + t2.weight, t1.value + t2.value};}

std::map<LL, std::map<LL, tuple>> dp{};
std::map<LL, std::map<LL, bool>> isdpable{};

tuple rec(const std::vector<tuple>& items, LL w, LL i = 0) {
    if (isdpable[i][w]) {
        return dp[i][w];
    }
    tuple retval;
    if (items.size() <= i) {
        retval = tuple{0,0};
    }
    else if (w < items.at(i).weight) {
        retval = rec(items, w, i + 1);    //i?????????????????????????????????
    } else {
        retval = std::max( rec(items, w - items[i].weight, i + 1) + items[i], //i???????????????????????????
                           rec(items, w, i + 1),                              //i?????????????????????????????????
                           [](auto a,auto b){
                               if (a == b) return a.weight > b.weight;
                               else return a < b;
                           });
    }
    dp[i][w] = retval;
    isdpable[i][w] = true;
    return retval;
}

void show_res(const tuple& resault) { 
    static LL i{1};
    std::cout << "Case " << i << ":" << std::endl;
    std::cout << resault.value << std::endl;
    std::cout << resault.weight << std::endl;
    i++;
}
void show_tup(const tuple& t) {
    std::cout << t.value << std::endl;
    std::cout << t.weight << std::endl;
}

int main(int argc, char const* argv[])
{
    for(;;){
        LL W{}, N{};
        std::vector<tuple> items{};
        std::cin >> W >> N;
        if (W==0) {
            break;
        }
        items.resize(N);
        for (LL i = 0; i < N; i++) {
            tuple input{};
            std::cin >> input.value;
            std::cin.ignore();
            std::cin >> input.weight;
            std::cin.ignore();
            items[i] = (input);
        }
        auto resault = rec(items, W);
        show_res(resault);
        dp.clear();
        isdpable.clear();
    }

    return 0;
}

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

int main(){
  long long int wi;
  long long int x=1;
  while(cin>>wi){
    if(wi==0)break;
    long long int n;
    cin>>n;
    vector<long long int> v(n);
    vector<long long int> w(n);
    char t;
    for(long long int i=0;i<n;i++)cin>>v[i]>>t>>w[i];
    vector<vector<long long int> > dp(1002,vector<long long int>(1002,0));

    for(long long int i=1;i<=n;i++){
      for(long long int j=0;j<=wi;j++){
        if(w[i-1]<=j){
          dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
        }else{
          dp[i][j]=max(dp[i][j],dp[i-1][j]);
        }
      }
    }

    /*
    for(int i=0;i<n;i++){
      for(int j=0;j<=wi;j++){
        cout<<dp[i][j]<<" ";
      }
      cout<<endl;
    }
    */

    long long int ans=0;
    long long int id=0;
    for(long long int i=0;i<=wi;i++){
      if(ans<dp[n][i])id=i;
      ans=max(ans,dp[n][i]);
    }
    cout<<"Case "<<x<<":"<<endl;
    cout<<ans<<endl;
    cout<<id<<endl;

    x++;
  }
}

C++: #include<stdio.h>
#include<string.h>
#include<math.h>
int a,s,d[1001],f[1001],g[1001][1001],h,i,j,z,x;
int main(void)
{
	x=1;
	while(1){
		scanf("%d",&a);
		if(a==0)	break;
		scanf("%d",&s);
		for(i=0;i<s;i++)
			scanf("%d,%d",&d[i],&f[i]);
		for(i=0;i<s;i++){
			for(j=0;j<=a;j++)
				g[i][j]=-1;
		}
		g[0][0]=0;
		for(i=0;i<s;i++){
			for(j=0;j<=a;j++){
				if(g[i][j]!=-1){
					if(g[i][j]>g[i+1][j])
						g[i+1][j]=g[i][j];
					if(j+f[i]<=a){
						if(g[i][j]+d[i]>g[i+1][j+f[i]])
							g[i+1][j+f[i]]=g[i][j]+d[i];
					}
				}
			}
		}
		h=0;
		z=0;
		for(i=0;i<=a;i++){
			if(h<g[s][i]){
				h=g[s][i];
				z=i;
			}
		}
		printf("Case %d:\n",x);
		printf("%d\n%d\n",h,z);
		x++;
	}
	return 0;
}

C++: import java.lang.*;
import java.util.*;

public class Main
{
    static Scanner sc = new Scanner(System.in);
    public static void main(String args[])
    {
	for(int k=1; ;k++){
	    int W = sc.nextInt();
	    if(W==0)break;
	    
	    int n = sc.nextInt();
	    
	    int[] dp = new int[W+1];
	    for(int i=0; i<W; i++){
		dp[i]=0;
	    }
	    
	    int dv,dw;
	    for(int i=0; i<n; i++){
		String[] s = sc.next().split(",");
		dv = Integer.parseInt(s[0]); //value
		dw = Integer.parseInt(s[1]); //weight
		for(int j=W; j>=0; j--){
		    if(j == dw) dp[j]=Math.max(dp[j], dv);
		    else if(dp[j] != 0 && j+dw <= W) dp[j+dw]=Math.max(dp[j+dw], dv+dp[j]);
		}
	    }
	      
	    int[] max = new int[2];
	    max[0] = -1; //[0]dv [1]i
	    for(int i=W; i>0; i--){
		if(max[0] <= dp[i]){
		    max[0] = dp[i];
		    max[1] = i;
		}
	    }
	    System.out.println("Case " + k + ":\n" + max[0] +"\n" + max[1]);
	}
    }
}

C++: #include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
#include<queue>
#include <functional>
using namespace std;

int main(){
  int w,n,t[1001][2];
  int memo[1111]={0};
  int ans=0;
  int omosa,kati;
  int nam=1;
  char a;
  
  while(1){
    ans=0;
    for(int i=0;i<1111;i++){
      memo[i]=0;
    }
    for(int i=0;i<1001;i++){
      for(int j=0;j<2;j++){
	t[i][j]=0;
      }
    }
    cin >> w;
    if(w == 0)break;
    cin >> n;
    for(int i=1;i<=n;i++){
      cin >> t[i][0] >> a >> t[i][1];
    }
    for(int i=0;i<=n;i++){
      omosa=t[i][1];
      kati=t[i][0];
      for(int j=i+1;j<=n;j++){
	if(omosa+t[j][1] < w){
	  omosa+=t[j][1];
	  kati+=t[j][0];
	  if(ans<kati){
	    ans=kati;
	  }
	  if(memo[omosa]<kati){
	    memo[omosa]=kati;
	  }
	}
      }
    }
    for(int i=0;i<=w;i++){
      if(memo[i]==ans){
	printf("Case %d:\n",nam);
	cout << ans << endl;
	cout << i << endl;
	nam++;
	break;
      }
    }
  }
}