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<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(correntWeight < 0)
	{

		Treasurea temp;
		temp.value = correntValue - treasurea[step- 1].value;
		temp.weight = W - (correntWeight + treasurea[step- 1].weight);
		return temp;

	}
	*/
	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
		{
			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);

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

		treasurea.erase(treasurea.begin(),treasurea.end());

	}

}

C++: #include<iostream>
#include<cstdio>
#include<string>
#include<vector>

using namespace std;

struct Treasure
{

  long value;
  long weight;
  bool flag;
};

bool flag;
long limit_weight;
long treasure_number;
Treasure result_treasure;

int AThief(vector<Treasure> &treasure,long &total_value,long &total_weight)
{

  if(limit_weight < total_weight){
    cout << "limit_weight" << endl;
    return 0;
  }
  else
    {

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

          if(treasure[i].flag)
            {

              total_value += treasure[i].value;
              total_weight += treasure[i].weight;
              treasure[i].flag = false;

              if(AThief(treasure,total_value,total_weight) == 0)
                {

                  total_value -= treasure[i].value;
                  total_weight -= treasure[i].weight;

                  if(result_treasure.value == total_value && result_treasure.weight > total_weight) result_treasure.weight = total_weight;
                  else if(result_treasure.value < total_value)
                    {
                      result_treasure.value = total_value;
                      result_treasure.weight = total_weight;
                    }
                  flag = false;
                }
              else
                {
                  total_value -= treasure[i].value;
                  total_weight -= treasure[i].weight;
                }

              treasure[i].flag = true;

            }

        }

    }

  //全部足しても耐えられる重さを越えなかった時
  if(flag)
    {
      result_treasure.value = total_value;
      result_treasure.weight = total_weight;
      flag = false;
    }


  return 1;

}


int main()
{

  int dummy;
  Treasure temp;
  int case_number = 0;
  long total_value = 0;
  long total_weight = 0;
  vector<Treasure> treasure;

  cin >> limit_weight;

  while(limit_weight!=0)
    {

      cin >> treasure_number;

      treasure.clear();

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

          scanf("%d,%d",&temp.value,&temp.weight);
          temp.flag = true;
          treasure.push_back(temp);

        }

      result_treasure.value = -1;
      result_treasure.weight = 2147483647;
      flag = true;
      dummy = AThief(treasure,total_value,total_weight);

      case_number++;

      cout << "Case " << case_number << ":" << endl;
      cout << result_treasure.value << endl;
      cout << result_treasure.weight << endl;

      cin >> limit_weight;

    }

}

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

int data[1000][2];
int dp[1000][1000];
int n,w;

int solve(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=w;j++){
			if(j >= data[i][1]){
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-data[i][1]]+data[i][0]);
			}else{
				dp[i][j] =dp[i-1][1];
			}
		}
	}
	return dp[n][w];
}

int solve2(){
	for(int i=0;i<=w;i++){
		if(dp[n][w] == dp[n][i]){
			return i;
		}
	}
	return w;
}

int main(){
	int casecount = 0;
	while(true){
		casecount++;
		cin>>w;
		if(w == 0){
			break;
		}
		memset(dp,0,sizeof(dp));

		cin >> n;
		for(int i=0;i<n;i++){
			scanf("%d,%d",&data[i][0],&data[i][1]);
		}
		
		cout << "Case " << casecount << ":" << endl;
		cout << solve() << endl;
		cout << solve2() << endl;
	}
}

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

int main(){
  int n,v[1000],w[1000],W,casenum = 0;
  int dp[1001][1001];
  const int INF = 100000000;
  
  while(scanf("%d",&W),W){
    casenum++;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d,%d",&v[i],&w[i]);
    
    for(int i=0;i<=W;i++)dp[0][i] = 0;

    int ansv = 0, answ = 0;
    for(int i=0;i<n;i++){
      for(int j=0;j<=W;j++){
	dp[i+1][j] = dp[i][j];
	if(j>=w[i] && dp[i+1][j] < dp[i][j-w[i]] + v[i]){
	  dp[i+1][j] = dp[i][j-w[i]] + v[i];
	  if( ansv < dp[i+1][j] || (ansv == dp[i+1][j] && answ > j) ){
	    ansv = dp[i+1][j]; answ = j;
	  }
	}
      }
    }
    
    printf("Case %d:\n",casenum);
    printf("%d\n%d\n",ansv,answ);
  }
}

C++: #include<iostream>
#include<algorithm>
#include<ios>
using namespace std;
int W,n,w,v;
int dp[1001];
int cnt;
main()
{
	while(cin>>W,W)
	{
		cnt++;
		cin>>n;
		for(int i=0;i<=W;i++)dp[i]=0;
		for(int i=0;i<n;i++)
		{
			scanf("%d,%d",&v,&w);
			for(int i=W;i>=w;i--)dp[i]=max(dp[i],dp[i-w]+v);
		}
		while(W>0&&dp[W]==dp[W-1])W--;
		cout<<"Case "<<cnt<<":\n"<<dp[W]<<"\n"<<W<<"\n";
	}
}