Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
	"fmt"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	Case := 1
	for {
		scanner.Scan()
		W, _ := strconv.Atoi(scanner.Text())
		if W == 0 {
			break
		}
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		w := make([]int, n+1)
		v := make([]int, n+1)
		for i := 1; i <= n; i++ {
			scanner.Scan()
			info := strings.Split(scanner.Text(), ",")
			v[i], _ = strconv.Atoi(info[0])
			w[i], _ = strconv.Atoi(info[1])
		}
		// fmt.Println(v)
		// fmt.Println(w)
		dp := make([][]int, n+1)
		for i := range dp {
			dp[i] = make([]int, W+1)
		}
		maxV := -(1 << 21)
		minW := 1 << 21
		for i := 1; i <= n; i++ {
			for j := 1; j <= W; j++ {
				// fmt.Println(dp)
				if j-w[i] >= 0 {
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
					if maxV < dp[i][j] {
						maxV = dp[i][j]
						minW = j
					} else if maxV == dp[i][j] {
						minW = min(minW, j)
					}
				} else {
					dp[i][j] = dp[i-1][j]
				}
			}
		}
		fmt.Printf("Case %d:\n", Case)
		Case += 1
		fmt.Println(maxV)
		fmt.Println(minW)
	}
}
func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

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