潜水员3tle.cpp

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

#include <iostream>
using namespace std;

const int A = 1000, B = 800, OO = 123456789;
int n, yy, dd, f[A][A]={0};

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