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<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int w[1000],v[1000];
int memo[1001][1001];
int dfs(int pos,int win){
    if(memo[pos][win]!=-1)return memo[pos][win];
    int res;
    if(pos<1)res=0;
    else if(win-w[pos-1]<0)res=dfs(pos-1,win);
    else res=max(dfs(pos-1,win),dfs(pos-1,win-w[pos-1])+v[pos-1]);
    return memo[pos][win]=res;
}
int main(){
    int W;
    for(int cnt=0;scanf("%d",&W),W;cnt++){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%d,%d",v+i,w+i);
        fill_n(*memo,1001*1001,-1);
        int ans=dfs(n,W);
        for(int i=W-1;i>=0;i--){
            if(ans==dfs(n,i))continue;
            printf("%d\n%d\n",ans,i+1);
            break;
        }

    }
    return 0;
}

C++: #include <iostream>

int solve (int);

int main(int argc, char const* argv[])
{
    int times = 0;

    while (true) {
        if(solve(++times) == 1) break;
    }
    return 0;
}

int solve(int times) {
    int max_weight, item_count;
    int prices[1000] = {0};
    int weights[1000] = {0};

    std::cin >> max_weight;
    if (max_weight == 0) return 1;

    std::cin >> item_count;

    for(int i = 0; i < item_count; i++) {
        int p, w;
        char c;
        std::cin >> p >> c >> w;

        prices[i]  = p;
        weights[i] = w;
    }

    int dp[1010] = {0};


    for (int i = 0; i < item_count; i++) {
        int tmp_dp[1010] = {0};

        tmp_dp[weights[i]] = prices[i];

        for (int j = 0; j < 1001; j++) {
            if (dp[j] == 0) continue;

            int plus_weight = j + weights[i];
            int plus_price  = dp[j] + prices[i];
            if (plus_weight > max_weight) continue;
            if (plus_weight >= 1001) continue;
            tmp_dp[plus_weight] = plus_price;
        }

        for (int i = 0; i <= max_weight; i++) {
            dp[i] = std::max(dp[i], tmp_dp[i]);
        }
    }

    int min_weight = 99999;
    int max_price  = 0;
    for (int i = 0; i <= max_weight; i++) {
        if (max_price < dp[i]) {
            max_price  = dp[i];
            min_weight = i;
        } else if (max_price == dp[i]) {
            min_weight = std::min(i, min_weight);
        }
    }

    std::cout << "Case " << times << ":" << std::endl;
    std::cout << max_price << std::endl;
    std::cout << min_weight << std::endl;

    return 0;
}

C++: #include <stdio.h>

int main(){
	int price[1000],weight[1000];
	int weight_MAX;
	int treasure;
	int i,j;
	int ans_p,ans_w,time;
	int dp[10000];

	time = 1;

	scanf("%d",&weight_MAX);

	while(weight_MAX != 0){

		scanf("%d",&treasure);

		for(i = 0; i < treasure; i++){
			scanf("%d,%d",&price[i],&weight[i]);
		}

		for(i = 0; i < weight_MAX; i++){
			dp[i] = 0;
		}

		for(i = 0; i < treasure; i++){
			for(j = weight_MAX; j >= weight[i]; j--){
				if(dp[j - weight[i]] + price[i] > dp[j]){
					dp[j] = dp[j - weight[i]] + price[i];
				}
			}
		}

		ans_p = 0;
		ans_w = 0;
		
		for(i = 0;i < weight_MAX; i++){
			if(ans_p < dp[i]){
				ans_p = dp[i];
				ans_w = i;
			}
		}
		printf("Case %d:\n%d\n%d\n",time,ans_p,ans_w);

		time++;

		scanf("%d",&weight_MAX);
	}
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>

using namespace std;

int N,W;

struct Treasurea
{

	int value;
	int weight;
	int flag;

	Treasurea()
	{

		value = 0;
		weight = 0;
		flag = false;

	}

};

struct Memo
{

	Treasurea record;
	bool flag;

	Memo()
	{

		flag = false;

	}

};

Memo memo[1001][1001];

Treasurea knapsack(vector<Treasurea> &treasurea, int correntWeight, int correntValue, int step)
{

	if(treasurea.size() == step)
	{

		Treasurea temp;
		temp.value = correntValue;
		temp.weight = W - correntWeight;
		return temp;

	}
	else if(memo[correntWeight][step].flag) return memo[correntWeight][step].record;


	Treasurea total;

	for(int i = 0; i < N; ++i)
	{

		if(treasurea[i].flag) continue;
			treasurea[i].flag = true;
		
		Treasurea temp;

		if(correntWeight - treasurea[i].weight >= 0)  temp = knapsack(treasurea,correntWeight - treasurea[i].weight, correntValue + treasurea[i].value, step + 1);
		else
		{
			step += 1;
			temp.value = correntValue;
			temp.weight = W - correntWeight;
		}

		if( (total.value < temp.value) || (total.value == temp.value && total.weight > temp.weight))	total = temp;

		treasurea[i].flag = false;

	}

	memo[correntWeight][step].record = total; 
	memo[correntWeight][step].flag = true;

	return total;

}

int main()
{

	int case_count = 0;
	
	while(cin >> W && W != 0)
	{
		
		cin >> N;

		vector<Treasurea> treasurea(N);
		Treasurea result;

		for(int i = 0; i < N; ++i)	scanf("%d,%d",&treasurea[i].value,&treasurea[i].weight);			

		result = knapsack(treasurea,W,0,0);

		memset(memo,0,sizeof(memo));

		cout << "Case " << ++case_count << ":" << endl << result.value << endl << result.weight << endl;

		treasurea.clear();

	}

}