4 拼拼图的小杉(1)(tle).cpp

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

#include <iostream>
using namespace std;

const int N = 1009;
int n, m, t, f[N][N]={0};

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