Cod sursa(job #3223081)

Utilizator _irina__irina tanase _irina__ Data 12 aprilie 2024 13:11:06
Problema Problema rucsacului Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

struct Obiect
{
   int prof, g;
   
};
Obiect ob[50001];

int main()
{
    int n, G;
       
    int i, j, dp[2][10001];
    
    fin>>n>>G;
    
    for(i=1; i<=n; i++)
        fin>>ob[i].g>>ob[i].prof;
        
    dp[1][ob[1].g] = ob[1].prof;
    dp[1][0] = 0;
    
    for(i=1; i<=n; i++)
    {
        int lin_c = i%2;
        int lin_a = 1 - i%2;
        
        for(j=0; j<=G; j++)
        {
            if(j >= ob[i].g)
            {
                int x = dp[lin_a][j - ob[i].g] + ob[i].prof;
                dp[lin_c][j] = max(x, dp[lin_a][j]);
            }
            
            else 
                dp[lin_c][j] = dp[lin_a][j];
        }
    }
    
    int maxi=0;
    
    for(i=1; i<=G; i++)
    {
       if(dp[n%2][i]>maxi) maxi=dp[n%2][i];
    }
    
    fout<<maxi;
       

}