叠放箱子2ac.cpp

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

// f[i][j]  前 j 个箱子中选择 i 个后还能承受的最大重量, -1 不存在
// f[0][0] = +OO
// f[i][j] = Max( -1, Min( f[i-1][j-1]-w[j], s[j]), f[i][j-1] )
// 结果为 Max( i | f[i][n] != -1 )   1 <= i <=n
// 滚动数组
#include <iostream>
using namespace std;

const int N = 1003, D = -1, OO = 2123456789;
int n, f[N][2], cur=0, pre=1;

int main(){
    f[0][cur] = f[0][pre] = OO;
    cin >>n;
    int i, j, k, w, s;
    for( j=1; j<=n; ++j ){
         cur = pre; pre = 1 - pre;
         cin >>w >>s;
         for( i=1; i<=j; ++i ){
              f[i][cur] = D;
              k = f[i-1][pre] - w;
              if( k > s ) k = s;
              if( f[i][cur] < k ) f[i][cur] = k;
              if( (i<j) && (f[i][cur]<f[i][pre]) ) f[i][cur] = f[i][pre];
         }
    }
    
    for( i=n; i; --i )
         if( f[i][cur] != D ) break;
    cout <<i <<endl;
    
    system( "pause" );
    return 0;
}