Cod sursa(job #3373580)

Utilizator Vcitor09Solcanu Victor Vcitor09 Data 7 noiembrie 2026 11:50:34
Problema Problema rucsacului Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct obiect{
    int val,greutate;
}v[10005];
int n,m,G,pmax,pcur,gcur,rez;
bool sol[10005];
bool comp( obiect a, obiect b){
    return 1LL*a.val*b.greutate>1LL*b.val*a.greutate;
}
void bkt(int k){
    if(k==n+1){
        rez=max(rez,pcur);
        return;
    }
    bool ok=0;
    pcur+=v[k].val;
    gcur+=v[k].greutate;
    if(gcur>G) {
        ok=1;
    }
    int gi=G-gcur;
    int pi=pcur;
    int i;
    for(i=k+1;i<=n && v[i].greutate<=gi;++i){
        pi+=v[i].val;
        gi-=v[i].greutate;
    }
    if(i<=n) pi+=1LL*gi*v[i].val/v[i].greutate;
    if(pi<=rez) {
        ok=1;
    }
    if(!ok)
        bkt(k+1);
    pcur-=v[k].val;
    gcur-=v[k].greutate;
    bkt(k+1);
}
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>G;
    for(int i=1;i<=n;++i){
        cin>>v[i].greutate>>v[i].val;
    }
    sort(v+1,v+n+1,comp);
    gcur=0;
    for(int i=1;i<=n;++i){
        if(v[i].greutate+ gcur<=G){
            gcur+=v[i].greutate;
            pmax+=v[i].val;
        }
    }
    rez=pmax;
    //cout<<gcur<<'\n';
    gcur=0;
    pcur=0;
    bkt(1);
    cout<<rez;
    return 0;
}