Cod sursa(job #2293793)
Utilizator | Arhire Andrei Andrei-27 | Data | 1 decembrie 2018 16:25:37 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include <iostream>
#include <fstream>
using namespace std;
const int NR = 10005 ;
ifstream f ("rucsac.in") ;
ofstream g ("rucsac.out") ;
int t [ 2 ][ NR ] ;
int main() {
int n , g ; f >> n >> g ;
while ( n -- )
{
int x , y ; f >> x >> y ;
for ( int i = 0 ; i + x <= g ; ++ i ) t [ ( n + 2 ) % 2 ][ i + x ] = max ( t [ ( n + 1 ) % 2 ][ i ] + y , t [ ( n + 1 ) % 2 ][ i + x ] ) ;
}
g << t [ 0 ][ g ] ;
return 0;
}