Pagini recente » Cod sursa (job #2672203) | Cod sursa (job #2480206) | Cod sursa (job #2917174) | Cod sursa (job #2324313) | Cod sursa (job #441296)
Cod sursa(job #441296)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
long max2(long a, long b)
{
return (a>b)?a:b;
}
long max3(long a, long b, long c)
{
return max2(a, max2(b,c));
}
int main()
{
long n, ho, u, max=0, i, j;
FILE *f=fopen("input.in", "r");
FILE *g=fopen("output.out", "w");
fscanf(f, "%ld %ld %ld", &n, &ho, &u);
long *h=(long *) malloc((n+1)*sizeof(long));
long *w=(long *) malloc((n+1)*sizeof(long));
long **m=(long **) malloc((n+1)*sizeof(long*));
for(i=0; i<=n; i++)
m[i]=(long *) malloc((ho+1)*sizeof(long));
for(i=1; i<=n; i++)
fscanf(f,"%ld %ld", &h[i], &w[i]);
//m[i][j] is the max weight one can obtaing using fruits from 1 to i and admitting a height limit of j
for(i=0; i<=ho; i++)
m[0][i]=0;
for(i=0; i<=n; i++)
m[i][0]=0;
for(i=1; i<=n; i++)
{
for(j=0; j<=ho; j++)
{
//check if iterating height is greater than current items height
//plus rising height. You can now add the current item to any
//previous items and you've increased this ones height by u
if(j >= h[i]+u)
{
m[i][j] = max2(m[i-1][j], w[i]+m[i-1][j-(h[i]+u)]);
}
//now check if iterating height is greater than current items height
//if it is you can take this item but it must be your first pick
else if(j >= h[i])
{
m[i][j] = max2(m[i-1][j], w[i]);
}
else
{
m[i][j] = m[i-1][j];
}
}
}
max=m[n][ho];
printf("%ld\n", max);
fprintf(g, "%ld", max);
for(i=0; i<=n; i++)
free(m[i]);
free(m);
fclose(f);
fclose(g);
return 0;
}