叠放箱子1ac.cpp

背包类问题浅析和一些背包类问题的解答源程序。

#include <iostream>
using namespace std;

const int N = 1009, J = 6004;
int n, w[N]={0}, s[N]={0}, f[J]={0};

int main(){
    cin >>n;
    int i, j;
    for( i=1; i<=n; ++i )
         cin >>w[i] >>s[i];
    
    for( i=n; i>0; --i )
    for( j=s[i]+w[i]; j>=w[i]; --j )
         if( f[j-w[i]] >= f[j] ) f[j] = f[j-w[i]] + 1;
    
    int ans = 0;
    for( j=6000; j>0; --j )
         if( ans < f[j] ) ans = f[j];
    cout <<ans <<endl;
    
    system( "pause" );
    return 0;
}