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 <bits/stdc++.h>
using namespace std;

struct Item{
	int v,w;
	int idx;	
};



const int INF = 1000000000;
class Knapsack{
public:
	struct DPInfo{
		int weight,trueValue;
		bool operator < (const DPInfo &op) const {
			return weight != op.weight ? weight < op.weight : trueValue > op.trueValue; // INVERSE!!
		}
	};

	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;
	}
	//??¢??????????????\?????¨??????????????§????????????????????????
	pair<Knapsack,Knapsack> devideItems(int valueThreshold) const{
		Knapsack low = *this, high = *this;
		low.items.clear();
		high.items.clear();
		for(int i = 0 ; i < items.size() ; i++){
			if( items[i].v <= valueThreshold){
				low.items.push_back(items[i]);
			}else{
				high.items.push_back(items[i]);
			}
		}
		return {low,high};
	}

	vector<DPInfo> makeDPtable(int itemscale) const{
		if( items.size() == 0 ){
			return vector<DPInfo>(1,{0,0});
		}
		Knapsack compressed = *this;
		int maximumValue = -INF;
		for( auto i : compressed.items ){
			maximumValue = max(maximumValue,i.v);
		}
		double rate = min(1.0,1.*itemscale/maximumValue);
		for( auto &i : compressed.items ){
			i.v = (int)(ceil(rate*i.v)+1e-9);
		}

		int scale = 0;
		for( auto &i : compressed.items ){
			scale += i.v;
		}
		vector<DPInfo> dp(scale+1,{INF,-INF});
		dp[0] = {0,0};
		int sum = 0;
		for(int i = 0 ; i < compressed.items.size() ; i++){
			if( compressed.used[i] ) continue;
			sum += compressed.items[i].v;
			for(int j = sum ; j >= compressed.items[i].v ; j--){
				DPInfo nextV;
				nextV.weight = dp[j-compressed.items[i].v].weight + compressed.items[i].w;
				nextV.trueValue = dp[j-compressed.items[i].v].trueValue + items[i].v;
				if( nextV < dp[j] ){
					dp[j].weight = nextV.weight;
					dp[j].trueValue = nextV.trueValue;
				}
			}
		}
		return dp;
	}

	int BigSmallDP(int valueThreshold) const{
		auto tmp = devideItems(valueThreshold);
		auto dp1 = tmp.first.makeDPtable(valueThreshold);
		auto dp2 = tmp.second.makeDPtable(valueThreshold);
		auto prepare = [](const vector<DPInfo> &dp){
			vector< pair<int,int> > tmp;
			vector< pair<int,int> > res;
			for(int i = 0 ; i < dp.size() ; i++){
				if( dp[i].weight == INF ) continue;
				pair<int,int> key = {dp[i].weight,dp[i].trueValue};
				tmp.push_back(key);
			}
			sort(tmp.begin(),tmp.end(),[](pair<int,int> a,pair<int,int> b){
				return make_pair(a.second,a.first) < make_pair(b.second,b.first);
			});
			for( auto key : tmp ){
				while( res.size() && res.back().first >= key.first ) res.pop_back();
				res.push_back(key);
			}
			return res;
		};
		vector< pair<int,int> > happySeq1 = prepare(dp1);
		vector< pair<int,int> > happySeq2 = prepare(dp2);
		
		int limit = maximumWeight - totalWeight;
		int j = happySeq2.size() - 1;
		pair<int,pair<int,int>> maximumPair = {-1,{-1,-1}};

		for(int i = 0 ; i < happySeq1.size() ; i++){
			while( j &&happySeq2[j].first > limit - happySeq1[i].first ) j--;
			if( happySeq2[j].first + happySeq1[i].first <=  limit) 
				maximumPair = max(maximumPair,{happySeq1[i].second+happySeq2[j].second,{happySeq1[i].first,happySeq2[j].first}});
		}
		cout << maximumPair.first << endl;
		cout <<  maximumPair.second.first + maximumPair.second.second << endl;
		
		return maximumPair.first;
	}
	
	// int iterativeKnapsack(int step){
		// int threshold = 10;
		// int cur = -1;
		// while(1){
			// threshold += step;
			// int nex = BigSmallDP(threshold);
			// if( cur == nex ){
				// cerr << threshold << endl;
				// return cur;
			// }
			// else cur = nex;
		// }
	// }
};



pair<int,vector<Item>> makeTestcase(int size){
	vector<Item> res;
	for(int i = 0 ; i < size ; i++){
		res.push_back({rand()%10000+1,rand()%10000+1,i});
	}
	int n = rand() % 10000 * size;
	return {n,res};
}



int main(){
	int w;
	
	int t = 1;
	while( cin >> w && w ){
		int n;
		vector<Item> items;
		cin >> n;
		for(int i = 0 ; i < n ; i++){
			int x,y;
			scanf("%d,%d",&x,&y);
			items.push_back({x,y,i});
		}
		cout << "Case "<< t++ << ":"<<endl;
		Knapsack(w,items).BigSmallDP(300);
		
	}
	// int trying = 2000;
	// int all = 0;
	// int suc = 0;
	// for(int i = 0 ; i < trying ; i++){
		// int n;
		// vector<Item> items;
		// tie(n,items) = makeTestcase(100);
		// Knapsack knap(n,items);
		// auto uso = knap.BigSmallDP(1000);
		// auto tru = knap.BigSmallDP(2000);

		// if( tru != uso ){
			// cerr << tru << " " << uso << " " << i << endl;
		// }else{
			// cerr << suc << endl;
			// suc++;
		// }
		// all++;
	// }
	// cerr << suc << "/" << all << endl;
}

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

using namespace std;

int main() {
	int n, W;
	char dummy;
	int count = 1;

	while( true ) {

		cin >> W;
		if(W == 0) {
			break;
		}
		cin >> n;

		vector< int > item_val(n);
		vector< int > item_wei(n);
		vector< vector< int > > nap(n + 1, vector< int >(W + 1, 0));

		for(int i = 0; i < n; i++) {
			cin >> item_val[i] >> dummy >> item_wei[i];
		}

		for(int i = 0; i < n; i++) {
			for(int j = 0; j <= W; j++) {
				if(j + item_wei[i] <= W) {
					nap[i + 1][j + item_wei[i]] = max(nap[i + 1][j + item_wei[i]], nap[i][j] + item_val[i]);
				}
				nap[i + 1][j] = max(nap[i + 1][j], nap[i][j]);
			}
		}

		int max_weight = W;
		int max_value = 0;
		for(int j = 0; j <= W; j++) {
			if(max_value < nap[n][j]) {
				max_value = nap[n][j];
				max_weight = j;
			}
		}

		cout << "Case " << count << ":" << endl;
		cout << max_value << "\n" << max_weight << endl;
		count++;

	}
}

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

using namespace std;

int main(void){
  int W,n,v[1000],w[1000],dp[1001][1001],t=1;

  while(cin >> W,W){
    cin >> n;

    for(int i=0;i<n;i++)
    scanf("%d,%d",&v[i],&w[i]);

    for(int i=0;i<1000;i++)
      for(int j=0;j<1000;j++)
	dp[i][j]=-1;
    
    for(int i=0;i<1000;i++){
      dp[0][i] = 0;
    }
    
    for(int i=0;i<n;i++)
      for(int j=0;j<=W;j++)
	if(j<w[i])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 " << t << ":" << endl;
    
    for(int i=W;i>=0;i--){
      if(dp[n][i] != dp[n][W]){
	cout << dp[n][W] << endl << i+1 << endl;
	break;
      }
    }
      t++;
  }

  return 0;
}