Dear Dynamic Programmer,

I was trying to solve UVA 10154 "Weights & Measures".
I first tried an DP LIS approach which is accepted by PC. However, UVA changed the test cases to reject this approach. and UVATOOLKIT is not helpful (it uses DP LIS solution).
Later, I was trying to write DP KNAP approach.

If any one can give me hints about the correct solution for this problem, I'll be grateful.

Here is my second try:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int best[6000][6000];
bool comp(pair<int, int> a, pair<int, int> b){
	return a.second > b.second;
}
int main(){
	vector<pair<int, int> > v;
	v.push_back(make_pair(0, 0));
	int C = 0;
	int w, s;
	while(cin >> w >> s){
		if(s-w>C) C = s-w;
		v.push_back(make_pair(w, s-w));
	}
	sort(v.begin()+1, v.end(), comp);
	int N = v.size();
	for(int i=0 ; i<=N ; i++)
		for(int j=0 ; j<=C ; j++)
			best[i][j] = 0;
	for(int i=1 ; i<=N ; i++){
		for(int j=1 ; j<=v[i].first+v[i].second ; j++){
			if(v[i].first<=j){
				best[i][j] = max(best[i-1][j], best[i-1][j-v[i].first]+1);
			}
			else{
				best[i][j] = best[i-1][j];
			}
		}
	}
	// For debugging only
	for(int i=0 ; i<=N ; i++){
			for(int j=0 ; j<=C ; j+=100){
					cout << best[i][j] << " ";
			}
			cout << endl;
	}
	cout << best[N][C] << endl;
	return 0;
}

Sorry, here it is:
http://uva.onlinejudge.org/external/101/10154.html5

The Problem

Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtles should be dispatched to form Yertle's throne. Each of the five thousand, six hundred and seven turtles ordered by Yertle has a different weight and strength. Your task is to build the largest stack of turtles possible.

Standard input consists of several lines, each containing a pair of integers separated by one or more space characters, specifying the weight and strength of a turtle. The weight of the turtle is in grams. The strength, also in grams, is the turtle's overall carrying capacity, including its own weight. That is, a turtle weighing 300g with a strength of 1000g could carry 700g of turtles on its back. There are at most 5,607 turtles.

Your output is a single integer indicating the maximum number of turtles that can be stacked without exceeding the strength of any one.

Sample Input
300 1000
1000 1200
200 600
100 101

Sample Output
3