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};}

const unsigned MAX_W = 1000;
const unsigned MAX_N = 1000;
std::array<std::array<tuple, MAX_W+1>, MAX_N+1> dp{};
std::array<std::array<bool, MAX_W+1>, MAX_N+1> 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);
        for (auto&& a : isdpable) {
            for (auto&& b : a) {
                b = false;
            }
        }
    }

    return 0;
}

C++: #include <iostream>
#include <string>
#include <math.h>
#include <map>
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include <stdlib.h>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;



int main() {
    int furosiki;
    int case_count = 1;

    
    while(cin>>furosiki){
        if(furosiki==0){
            break;
        }
        
        
        
        int num;
        cin>>num;
        size_t bits;
        bits = num;
        bitset<1000> bs;
        
        
        int val[num];
        int wei[num];
        for(int i=0; i<num; i++)scanf("%d,%d",&val[i],&wei[i]);
        int binary_max=1;
        for(int i=0; i<num; i++)binary_max*=2;
        int max_val = 0;
        int max_wei = 0;
        for(int i=0; i<=binary_max; i++){
            bs = i;
            int temp_val=0;
            int temp_wei=0;
            for(int j=0; j<num; j++){
                temp_val+=bs[j]*val[j];
                temp_wei+=bs[j]*wei[j];
            }
            if(temp_wei<=furosiki){
                if(max_val<temp_val){
                    max_val=temp_val;
                    max_wei=temp_wei;
                }else if(max_val==temp_val && max_wei>temp_wei){
                    max_val=temp_val;
                    max_wei=temp_wei;
                }
            }
        }
        cout<<"Case "<<case_count<<":"<<endl;
        cout<<max_val<<endl;
        cout<<max_wei<<endl;
        case_count++;
    }
    
    
    return 0;
}

C++: #include "bits/stdc++.h"

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

int dp[2000][2000];



int main(){
	int W;
	int n;
	int c=0;
	while(cin>>W){
		c++;
		if(W==0)break;
		char ch;
		int w[2000],v[2000];
		rep(i,2000)rep(j,2000)dp[i][j]=-999;
		cin>>n;
		rep(i,n){
			cin>>v[i]>>ch>>w[i];
		}

		int maxval=-1;
		int maxwait=-1;

		dp[0][0]=0;
		rep(i,n){
			rep(j,W){
				if(i-1>=0){
					dp[i][j] = max(dp[i][j],dp[i-1][j]);
					if(j-w[i]>=0)
						dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i] );
					if(maxval<dp[i][j]){
						maxval=dp[i][j];
						maxwait=j;
					}
					if(maxval==dp[i][j] && maxwait>j){
						maxval=dp[i][j];
						maxwait=j;
					}

				}
			}
		}
		cout<<"Case "<<c<<":"<<endl;
		cout<<maxval<<endl;
		cout<<maxwait<<endl;
	}
}

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

	int w,n,cnt=1;
	int dp[1006][10005],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++)V[i]=W[i]=0;
		for(int i=0;i<1006;i++)fill(dp[i],dp[i]+10005,0);
	}
	return 0;
}