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<cstdio>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int,int> P;

int main(){
	int W,N,cou=0;
	int tr[1001],we[1001];
	while(cin >> W , W){
		cou++;
		cin >> N;
		for(int i=0;i<N;i++){
			scanf("%d,%d",&tr[i],&we[i]);
		}

		int dp[1010];
		for(int i=0;i<=N;i++){
			dp[i]= 0;
		}
		for(int i=0;i<N;i++){
			for(int j=W;j>=we[i];j--){
				dp[j] = max(dp[i],dp[j-we[i]]+tr[i]);
			}
		}
		int ret = 0;
		for(int i=0;i<=W;i++){
			if(dp[i] > dp[ret]) ret = i;
		}
		cout << "Case " << cou << ":" << endl;
		cout << dp[ret] << endl;
		cout << ret << endl;
	}
}

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

struct Item{
	int v,w;
	int idx;	
};
const int INF = 1000000000;
class Knapsack{
public:
	
	
	int maximumWeight;
	vector<Item> items;
	Knapsack(int maximumWeight_,vector<Item> items_) : maximumWeight(maximumWeight_),items(items_) {
		used.resize(items.size(),false);
		totalWeight = totalValue = 0;
		sort(items.begin(),items.end(),[](Item a,Item b){ return a.v * b.w > b.v * a.w; });
	}
	int totalValue;
	int totalWeight;
	vector<bool> used;
	bool operator < (const Knapsack &op) const {
		if( totalValue == op.totalValue )
			return totalWeight > op.totalWeight;
		return totalValue < op.totalValue;
	}

	bool canPut(const Item &x){
		return !used[x.idx] && x.w <= maximumWeight - totalWeight;
	}
	bool putItem(const Item &x){
		if( canPut(x) ){
			totalWeight += x.w;
			totalValue += x.v;
			used[x.idx] = true;
			return true; // success
		}else{
			return false; // failure
		}
	}
	bool removeItem(const Item &x){
		if( used[x.idx] ){
			totalWeight -= x.w;
			totalValue -= x.v;
			used[x.idx] = false;
			return true;
		}
		return false;
	}
	int swapAtoB(Item x,Item y){
		if( used[x.idx] && !used[y.idx] ){
			if( totalWeight - x.w + y.w > maximumWeight ) return -INF;
			return y.v - x.v;
		}else{
			return -INF;
		}
	}
	Knapsack knapSackDP(int scale) const{
		Knapsack res = *this;
		int maximumValue = -INF;
		for( auto i : res.items ){
			maximumValue = max(maximumValue,i.v);
		}

		double rate = min(1.0,1.*scale/maximumValue);
		for( auto &i : res.items ){
			i.v = (int)(ceil(rate*i.v)+1e-9);
		}
		
		vector<int> dp(scale+1,INF),lastId(scale+1,-1);
		dp[0] = 0;
		for(int i = 0 ; i < res.items.size() ; i++){
			if( res.used[i] ) continue;
			for(int j = scale ; j >= res.items[i].v ; j--){
				if( dp[j-res.items[i].v] + res.items[i].w < dp[j] ){
					dp[j] = dp[j-res.items[i].v] + res.items[i].w;
					lastId[j] = i;
				}
			}
		}
		for(int i = scale ; i >= 0 ; i--){
			if( dp[i] <= maximumWeight - totalWeight ){
				int cur = i;
				while(cur > 0){
					int p = lastId[cur];
					res.putItem(res.items[p]);
					cur -= res.items[p].v;
					if( p == -1 ) exit(0);
				}
				break;
			}
		}
		return res;
	}
	Knapsack localImprovement() const{
		Knapsack res = *this;
		while(true){
			// ????¬??????????????????????????????§??????????
			for(int i = 0 ; i < res.items.size() ; i++){	
				res.putItem(res.items[i]);
			}
			auto reflesh = [&](){
				for(int i = 0 ; i < res.items.size() ; i++){
					if( res.used[i] ){

						auto tmp = res;
						tmp.removeItem(tmp.items[i]);
						for(int j = 0 ; j < tmp.items.size() ; j++){
							if( i != j && !tmp.used[j] ){	
								tmp.putItem(tmp.items[j]);
							}
						}
						if( res < tmp ){
							res = tmp;
							return true;
						}
					}
				}
				return false;
			};
			if( reflesh() ) continue;
			
			auto reflesh2 = [&](){
				for(int i = 0 ; i < res.items.size() ; i++){
					if( res.used[i] ){

						for(int j = 0 ; j < res.items.size() ; j++){
							if( !res.used[j] ){
								if( res.swapAtoB(res.items[i],res.items[j]) >= 0 ){
									res.removeItem(res.items[i]);
									res.putItem(res.items[j]);
									return true;
								}
							}
						}
					}
				}
				return false;
			};
			if( reflesh2() ) continue;
			break;
		}
		return res;
	}
};




int main(){
	int n,m;
	int t=1;
	while(cin >> n >> m && n){
		vector<Item> items;
		for(int i = 0 ; i < m ; i++){
			int x,y;
			scanf("%d,%d",&x,&y);
			items.push_back({x,y,i});
		}
		Knapsack knap(n,items);
		knap = knap.knapSackDP(15000);
		cout << "Case " << t++ << ":" << endl;
		//knap = knap.localImprovement();
		cout << knap.totalValue << "\n" << knap.totalWeight << endl;
	}
}

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

int W;
int w[1001],v[1001];
int N;
int dp[1001][1001];

int rec(int i, int j){

  //テ」ツつづ」ツ??」ツつ?」ツ?」テ」ツ??
  if(dp[i][j] >= 0){
    return dp[i][j];
  }
  int res;

  if(i == N){ // テ」ツつづ」ツ??・ツ督?ァツ可ゥテ」ツ?ッテァツ?。テ」ツ??
    res = 0;

  }else if(j < w[i]){ // テ」ツ?禿」ツ?ョテ・ツ督?ァツ可ゥテ」ツ?ッテ・ツ?・テ」ツつ嘉」ツ?ェテ」ツ??
    res = rec(i + 1,j);
 
  }else{ // テ・ツ督?ァツ可ゥテ」ツつ津・ツ環?」ツ?暗」ツつ凝」ツ?禿」ツ?ィテ」ツ?古・ツ?コテヲツ敖・テ」ツつ凝」ツ?ィテ」ツ??
        res = max(rec(i+1,j), rec(i+1,j-w[i]) + v[i]);
    /* 
   int tmp1,tmp2;
    tmp1 = rec(i+1,j);
    tmp2 = rec(i+1,j-w[i]) + v[i];
    if(tmp1 < tmp2){
      res = tmp2;
    }else{
      res = tmp1;
    }
    */
  }
  return dp[i][j] = res;
}


int main(){

  int num = 1;

  while(1){
    cin >> W;
    if(W == 0) break;
    cin >> N;
    //テ・ツ按敕ヲツ慊淌・ツ個?
    /*
    for(int i = 0; i < 1001; i++){
      w[i] = v[i] = -1;
      for(int j = 0; j < 1001; j++)
	dp[i][j] = -1; 
    }
    */
    memset(dp,-1,sizeof(dp));
    memset(w,-1,sizeof(w));
    memset(v,-1,sizeof(v));


    //テ・ツ?・テ・ツ環?
    char tmp;
    for(int i = 0; i < N; i++) cin >> v[i] >> tmp >> w[i];

    int ans = rec(0,W);

    // dpテゥツ?催・ツ按療」ツつ津・ツ?ィテ」ツ?ヲテ・ツ淞凝」ツつ?」ツつ?
    for(int i = 0; i < N; i++){
      for(int j = 0; j <= W; j++){
	if(dp[i][j] == -1)
	  rec(i,j);
      }
    }   
  
    cout << "Case "<< num  << ":"<< endl;
    num++;
    cout << ans << endl; 
    int j;
    for( j = 0; dp[0][j] != ans ; j++){}
    cout << j << endl;
    
  }
  return 0;
}

C++: #include <stdio.h>

int takara[1024][1024];

int main(void)
{
	int i, j;
	int n;
	int w;
	int t[1024];
	int we[1024];
	int max;
	int c;
	
	c = 0;
	while (scanf("%d", &w), w != 0){
		scanf("%d", &n);
		for (i = 0; i <= n; i++){
			for (j = 0; j <= w; j++){
				takara[i][j] = 0;
			}
		}
		for (i = 0; i < n; i++){
			scanf("%d,%d", &t[i], &we[i]);
		}
		for (i = 0; i < n; i++){
			for (j = 0; j <= w; j++){
				if (takara[i + 1][j] < takara[i][j]){
					takara[i + 1][j] = takara[i][j];
				}
				if (takara[i + 1][j + we[i]] < takara[i][j] + t[i]){
					takara[i + 1][j + we[i]] = takara[i][j] + t[i];
				}
			}
		}
		
		for (i = 0; i <= n; i++){
			for (j = 0; j <= w; j++){
				printf("%4d", takara[i][j]);
			}
			printf("\n");
		}
		max = 0;
		for (i = 0; i <= w; i++){
			if (takara[n][i] > takara[n][max]){
				max = i;
			}
		}
		printf("Case %d:\n%d\n%d\n", c + 1, takara[n][i], max);
		c++;
	}
	return (0);
}