Pagini recente » Cod sursa (job #448075) | Cod sursa (job #3201698) | Cod sursa (job #39829) | Cod sursa (job #337334) | Cod sursa (job #442283)
Cod sursa(job #442283)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define file_in "gutui.in"
#define file_out "gutui.out"
typedef struct fruit_
{
long int height;
long int weight;
} fruit;
fruit *fruits, *solution;
long int N, U, H, *used, max = 0;
void bkt(int ind, fruit *solution)
{
long int i, sum;
if(solution[ind-1].height + U*ind > H)
{
sum = 0;
for(i=0;i<ind;i++)
sum += solution[i].weight;
if(max < sum)
max = sum;
}
else
{
for(i=0;i<N;i++)
{
if(!used[i])
{
solution[ind] = fruits[i];
if(solution[ind].height + U*(ind-1) <= H)
{
used[i] = 1;
bkt(ind+1, solution);
used[i] = 0;
}
}
}
}
}
int main()
{
long int i;
freopen(file_in, "rt", stdin);
freopen(file_out, "wt", stdout);
scanf("%li %li %li", &N, &H, &U);
fruits = (fruit *)malloc(N*sizeof(fruit));
solution = (fruit *)malloc(N*sizeof(fruit));
used = (long int *)malloc(N*sizeof(long int));
memset(used, 0, N*sizeof(long int));
for(i = 0; i < N; i++)
scanf("%li %li", &fruits[i].height, &fruits[i].weight);
bkt(0,solution);
printf("%li",max);
free(fruits);
free(solution);
free(used);
fclose(stdin);
fclose(stdout);
return 0;
}