4 拼拼图的小杉(2).cpp

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

#include <iostream>
using namespace std;

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

int main(){
    int i, j, v, fa, fb, ga, gb, ans;
    cin >>n >>m >>t;
    
    for( i=0; i<=n; ++i ){
         g[0][i] = t;
    }
    
    for( j=1; j<=n; ++j ){
         cin >>v;
         
         // f[j][j]
         if( g[j-1][j-1]+v > t ){
             f[j][j] = f[j-1][j-1] + 1;
             g[j][j] = v;
         }
         else{
              f[j][j] = f[j-1][j-1];
              g[j][j] = g[j-1][j-1] + v;
         }
         
         // f[i][j]
         for( i=1; i<j; ++i ){
              // fa, ga
              if( g[i-1][j-1]+v > t ){
                  fa = f[i-1][j-1] + 1;
                  ga = v;
              }
              else{
                   fa = f[i-1][j-1];
                   ga = g[i-1][j-1] + v;
              }
              
              // fb, gb
              fb = f[i][j-1];
              gb = g[i][j-1];
              
              // f[i][j]
              if( (fa<fb) || ( (fa==fb) && (ga<gb) ) ){
                  f[i][j] = fa;
                  g[i][j] = ga;
              }
              else{
                   f[i][j] = fb;
                   g[i][j] = gb;
              }
         }
    }
    
    for( i=n; i>=0; --i )
         if( f[i][n] <= m ){
             ans = i;   break;
         }
    cout <<ans <<endl;
    system( "pause" );
    return 0;
}