~cpp
#include <iostream> 
using namespace std; 
#include <vector> 
#include <algorithm> 

const int maxweight = 10000000; 

typedef struct  
{ 
    int weight; 
    int strength; 
}turtle; 

bool compare(const turtle & a, const turtle & b) 
{ 
    return a.strength < b.strength; 
}

int main() 
{ 
     
    turtle temp; 
    vector<turtle> test; 
	int value[5608]; 
    int tem;
	int max =test.size(); 
    
	temp.strength = temp.weight = 0; 
    test.push_back(temp);
     
    while(cin >> temp.weight >> temp.strength) 
    { 
        test.push_back(temp); 
    } 
         
    sort(test.begin(), test.end(), compare); 
         
    for(int i = 1; i < max; i++) 
    { 
        value[i] = maxweight; 
    } 
    value[0] = 0; 
     
    for(i = 1; i < max; i++) 
    { 
        for(int j = i; j != 0 ; j--) 
        { 
            tem = value[j-1] + test[i].weight; 
            if( tem <= test[i].strength) 
            { 
                value[j] = (tem < value[j]? tem:value[j]); 
            } 
        } 
    } 
     
    while(value[--max] == maxweight); 
     
    cout << max << "\n"; 
     
    return 0; 
} 
Retrieved from http://wiki.zeropage.org/wiki.php/WeightsAndMeasures/김상섭
last modified 2021-02-07 05:28:24