Pagini recente » Cod sursa (job #2412875) | Cod sursa (job #2738681) | Cod sursa (job #3133231) | Cod sursa (job #567635) | Cod sursa (job #673858)
Cod sursa(job #673858)
//asta e doar o aproximare greedy; se pare ca pe infoarena i-a 0 pct;
#include<fstream>
#include<algorithm>
#define DIM 5000
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int N;
float G;
float castig_total;
struct obiect
{
int weight, profit;
float raport;
}O[DIM];
bool comp(const obiect &unu, const obiect &doi)
{
return unu.raport > doi.raport;
}
int main()
{
int i, local_profit, local_weight, gasit = 0;
in >> N >> G;
for(i = 1; i <= N; i++)
{
in >> O[i].weight >> O[i].profit;
O[i].raport = O[i].profit/O[i].weight;
}
sort(O+1, O+N+1, comp);
i = 1;
local_profit = 0;
local_weight = 0;
while( local_weight < G && i <= N && !gasit )
{
if( O[i].weight <= G - local_weight )
{
local_weight += O[i].weight;
local_profit += O[i].profit;
}
else {
castig_total = local_profit + (G-local_weight)*O[i].raport;
gasit = 1;
}
i++;
}
out << castig_total;
}