数字游戏.cpp

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

#include <iostream>
using namespace std;

const int N = 2009;
int n, m, a[N], b[N], f[N]={0};
void QSort( int h, int t );   // b >= >=

int main(){
    cin >>n >>m;
    int i, j, k;
    for( i=1; i<=n; ++i ) cin >>a[i];
    for( i=1; i<=n; ++i ) cin >>b[i];
    QSort( 1, n );
    
    for( i=1; i<=n; ++i )
    for( j=m; j>0; --j )
         if( (k=f[j-1]-b[i]*(j-1)+a[i]) > f[j] ) f[j] = k;
    cout <<f[m] <<endl;
    
    system( "pause" );
    return 0;
}

void QSort( int h, int t ){
     int i=h, j=t, x=a[i], y=b[i];
     while( i<j ){
            while( (i<j) && (y>=b[j]) ) --j;
            if( i<j ){
                a[i] = a[j];   b[i] = b[j];  ++i;
            }
            while( (i<j) && (b[i]>=y) ) ++i;
            if( i<j ){
                a[j] = a[i];   b[j] = b[i];  --j;
            }
     }
     a[i] = x;   b[i] = y;
     if( h<i-1 ) QSort( h, i-1 );
     if( i+1<t ) QSort( i+1, t );
     return;
}