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 <algorithm>
using namespace std;

struct treasure{
	int value;
	int weight;
};

bool comp(treasure t1, treasure t2){
	if(t1.weight <= t2.weight) return true;
	else return false;
}

int main(){
	int w;
	const int maxw = 10000;
	int count = 1;
	while(cin >> w){
		if(w == 0) break;
		int n;
		int cost[maxw + 1];
		int best[maxw + 1];
		for(int i = 0; i <= maxw; i++){
			cost[i] = 0;
			best[i] = 0;
		}
		vector<treasure> treasures;
		cin >> n;
		for(int i = 0; i < n; i++){
			treasure t;
			char c;
			cin >> t.value >> c >> t.weight;
			treasures.push_back(t);
		}
		sort(treasures.begin(), treasures.end(), comp);
		for(int j = 0; j < n; j++){
			for(int k = 1; k <= w; k++)
				if(k >= treasures[j].weight)
					if(cost[k] < cost[k - treasures[j].weight] + treasures[j].value)
					{
						cost[k] = cost[k - treasures[j].weight] + treasures[j].value;
						best[k] = j;
					}
		}
		cout << "Case" << " " << count++ << ":" << endl;
		for(;w>0; w--) if(cost[w] != cost[w-1]) break;
		cout << cost[w] << endl;
		int total = 0;
		for(int l = w; l - treasures[best[l]].weight >= 0;){
			if(l - treasures[best[l]].weight >= 0){
				total += treasures[best[l]].weight;
				l -= treasures[best[l]].weight;
			}
		}
		cout << total << endl;
	}
	return 0;
}

C++: #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

short dk[10001][1001];

int main(){
	int i,j,takara[1001][2],w,n,c,maxv;
	c=0;
	while(0<=scanf("%d",&w)){
		if(w==0)break;
		scanf("%d",&n);
		++c;
		
		for(i=1;i<=n;i++){
			scanf("%d,%d",&takara[i][0],&takara[i][1]);
		}
		
		memset(dk,0,sizeof(dk));
		
		for(i=1;i<=n;i++){
			for(j=1;j<=w;j++){
				if(j>=takara[i][1]){
					dk[i][j]=(dk[i-1][j-takara[i][1]]+takara[i][0]>dk[i-1][j] ? dk[i-1][j-takara[i][1]]+takara[i][0]:dk[i-1][j]);
					continue;
				}
				dk[i][j]=dk[i-1][j];
			}
		}
		
		maxv=dk[n][w];
		
		for(i=0;i<=w;i++){
			if(maxv==dk[n][i])break;
		}
		
		printf("Case %d:\n",c);
		printf("%d\n%d\n",maxv,i);
	}
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = 1000, MAX_W = 1000;

int main(){
	int dp[MAX_N+1][MAX_W+1], wdp[MAX_N+1][MAX_W+1];
	int W,N,v[MAX_N],w[MAX_N],C = 1;
	while(cin >> W,W){
		memset(dp,0,sizeof(dp));
		memset(v,0,sizeof(v));
		memset(w,0,sizeof(w));
		std::cin >> N;
	for(int i=0;i<N;i++){
		int a,b;
		scanf("%d,%d",&a,&b);
		v[i] = a, w[i] = b;
	}
	for(int i=N-1;i>=0;i--){
		for(int j=0;j<=W;j++){
			if(w[i] > j)
				dp[i][j] = dp[i+1][j];
			else{
				dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]] + v[i]);
			}
		}
	}
	int wmv;
	for(int i=0;i<=W;i++){
		if(dp[0][i] == dp[0][W]){wmv = i;break;}
	}
	cout << "Case " << C++ << ":" << endl << dp[0][W] << endl << wmv << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	int w;
	const int maxw = 1000;
	int count = 1;
	int register cost[maxw + 1];
	int register best[maxw + 1];
	for(int i = 0; i <= maxw; i++){
		cost[i] = 0;		
		best[i] = 0;
	}
	int register values[maxw + 1];
	int register weights[maxw + 1];

	while(cin >> w){
		if(w == 0) break;
		int n;
		cin >> n;
		for(int i = 0; i < n; i++){
			char c;
			cin >> values[i] >> c >> weights[i];
		}
		for(int j = 0; j < n; j++){
			for(int k = 1; k <= w; k++)
				if(k >= weights[j])
					if(cost[k] < cost[k - weights[j]] + values[j])
					{
						cost[k] = cost[k - weights[j]] + values[j];
						best[k] = j;
					}
		}
		cout << "Case" << " " << count++ << ":" << endl;
		for(;w>0; w--) if(cost[w] != cost[w-1]) break;
		cout << cost[w] << endl;
		int total = 0;
		for(int l = w; l - weights[best[l]] >= 0;){
			if(l - weights[best[l]] >= 0){
				total += weights[best[l]];
				l -= weights[best[l]];
			}
		}
		cout << total << endl;
		for(int i = 0; i <= w; i++){
			cost[i] = 0;
			best[i] = 0;
		}
	}
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
using namespace std;

struct Treasure{
	int Weight;
	int Worth;
};
vector<int> TempMaxWorth;

int GetMaxWorth(const int MaxWeight,vector<Treasure> nowTreasureCollection, vector<Treasure>::iterator nowIterator,const vector<Treasure>& AllTreasureCollection){
	vector<Treasure>::iterator rootIterator(nowIterator);
	for (; nowIterator!=AllTreasureCollection.end(); ++nowIterator){
		nowTreasureCollection.push_back(*(nowIterator));
		const int NowWorth = accumulate(nowTreasureCollection.cbegin(),
			nowTreasureCollection.cend(),
			0,
			[](const int q, const Treasure& p){return q + p.Worth; }
		);
		const int NowWeight = accumulate(nowTreasureCollection.cbegin(),
			nowTreasureCollection.cend(),
			0,
			[](const int q, const Treasure& p){return q + p.Weight; });
		if (NowWeight <= MaxWeight&&NowWorth > TempMaxWorth[NowWeight]){
			TempMaxWorth[NowWeight] = NowWorth;
			replace_if(TempMaxWorth.begin() + NowWeight, TempMaxWorth.end(), [=](int n){return NowWorth > n; }, NowWorth);
			if((nowIterator+1)!=AllTreasureCollection.end())GetMaxWorth(MaxWeight, nowTreasureCollection, nowIterator+1,AllTreasureCollection);
		}
		nowTreasureCollection.pop_back();
	}
	nowIterator = (rootIterator);
	return 0;
}

int main(){
	int MaxWeight;
	int TreasureNum;
	for (int i = 1; cin >> MaxWeight;++i){
		if (MaxWeight == 0)return 0;
		cin  >> TreasureNum;
		TempMaxWorth.resize(MaxWeight + 1);
		fill(TempMaxWorth.begin(), TempMaxWorth.end(), 0);
		vector<Treasure> AllTreasureCollection;
		for (int j = 0; j < TreasureNum; ++j){
			Treasure T;
			cin >> T.Worth;
			cin.get();
			cin >> T.Weight;
			AllTreasureCollection.push_back(T);
		}	
		vector<Treasure> NowTreasureCollection = {};
		GetMaxWorth(MaxWeight, NowTreasureCollection, AllTreasureCollection.begin(), AllTreasureCollection);
		cout << "Case " << i << ":" << endl << TempMaxWorth[MaxWeight] << endl << find(TempMaxWorth.cbegin(), TempMaxWorth.cend(), TempMaxWorth[MaxWeight]) - TempMaxWorth.cbegin() << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
	int dp[1001][1001];
	int w[1001],v[1001],n,W;
	char s;
	int k=1;
	while(1){
		cin>>W>>n;
		if(W==0)break;
		for(int i=0;i<n;i++){
			cin>>v[i]>>s>>w[i];
		}
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++){
			for(int j=0;j<=W;j++){
				if(w[i]>j)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 "<<k<<endl;
		cout<<dp[n][W]<<endl;
        for(int i=0;i<=W;i++){
            if(dp[n][W]==dp[n][i]){
                cout<<i<<endl;;
                break;
            }
        }
		k++;
	}
}