潜水员1ac.cpp

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

#include <iostream>
using namespace std;

const int T = 60, A = 200, OO = 123456789;
int n, yy, dd, f[T][A];

int main(){
    int y, d, w, y0, d0, i, j;
    cin >>yy >>dd;
    for( i=0; i<=yy; ++i )
    for( j=0; j<=dd; ++j )
         f[i][j] = OO;
    f[0][0] = 0;
    for( cin >>n; n; --n ){
         cin >>y >>d >>w;
         for( i=yy; i>=0; --i )
         for( j=dd; j>=0; --j ){
              y0 = i + y; if( y0>yy ) y0 = yy;
              d0 = j + d; if( d0>dd ) d0 = dd;
              if( f[y0][d0] > f[i][j] + w )
                  f[y0][d0] = f[i][j] + w;
         }
    }
    
    cout <<f[yy][dd] <<endl;
    
    system( "pause" );
    return 0;
}