Pagini recente » Cod sursa (job #1602445) | Cod sursa (job #737866) | Cod sursa (job #2421514) | Cod sursa (job #1379979) | Cod sursa (job #2392949)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,g,i,a[10000], c[10000],suma,cost;
double b[10000];
fi>>n>>g;
for (i=1; i<=n; i++) {fi>>a[i]>>c[i]; b[i]=1.0*c[i]/a[i]; }
for (i=1; i<=n; i++)
for (int j=i+1; j<=n; j++) if (b[j]>b[i]) {swap(a[j],a[i]); swap(c[j],c[i]); swap(b[j],b[i]);}
suma=0; cost=0; i=1;
while (suma+a[i]<=g) {suma=suma+a[i]; cost=cost+c[i]; i++;}
cost=(g-suma)*b[i]+cost;
fo<<cost;
return 0;
}