Fruit Harvest Algorithm

[Slobodino]

I need an algorithm for the following problem:
There's a tree with N fruits each with its own weight w and height h. I can only reach a fruit if it's no taller than H inches. Also every time I pick a fruit, all the other fruits in the tree rise by exactly U inches. I need to find out the maximum amount (total weight) of fruits I can collect.

[Adak]

You haven't given enough information to solve the problem, yet.

[craig_ka]

Have you tried to do anything yet, I'd like to help but I won't do you program from start to finish. It looks like it could be solved using a 0-1 knapsack with slight modification for the heights changing as you pick. If you post some code you're working/stuck on I can try to help you. If you have nothing yet look up the 0-1 knapsack on wiki and at least you can get an idea of how to solve this.

[Slobodino]

Here's my code, I tried to adapt the solution of the knapsack problem to solve this one, however not to much success, since I've not figured out how to implement the increase of heights well.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

long u;
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, max=0;
	long h[100001], w[100001], i, j;
	
	FILE *f=fopen("input.in", "r");
	FILE *g=fopen("output.out", "w");
	fscanf(f, "%ld %ld %ld", &n, &ho, &u);
	
	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=1; j<=ho; j++)
	{
		if(h[i]+(u*(i-1))>j)
		m[i][j]=m[i-1][j];
		if(h[i]+(u*(i-1))<=j)
		m[i][j]=max3(m[i-1][j], m[i-1][j-1]+w[i], m[i][j-1]);
	}
	max=m[n][ho];
	fprintf(g, "%ld", max);
	
	for(i=0; i<=n; i++)				
	free(m[i]);
	free(m);	
	fclose(f);
	fclose(g);
	return 0;
}

I said what each variable represents in the original post. One thing I forgot to mention is that this program ought to work with big numbers, so it's no eccentricity of mine that I'm using long type.

[craig_ka]

without any example input and expected output I'm not 100% positive that this will work but I'm almost positive that this should do the trick.
Notice I changed j which iterates through possible heights to start at 0. Yours starting at 1 is fine as long as you are guaranteed not to have any fruit at height 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];
      }
   }
}

also, you're declaring your h, and w as statically sized even though you made your m variable dynamic. It would only take a few extra lines of code to size h and w to be able to hold n+1 elements at runtime.
I'm glad to see that you did look up the knapsack and made a good attempt at modifying it for this use. It looks like your problem with adding an item to the sack is that you used h+u*(i-1) which is assuming that every item before the current one has been added

[nezachem]

Have you tried to do anything yet, I'd like to help but I won't do you program from start to finish. It looks like it could be solved using a 0-1 knapsack with slight modification for the heights changing as you pick. If you post some code you're working/stuck on I can try to help you. If you have nothing yet look up the 0-1 knapsack on wiki and at least you can get an idea of how to solve this.

Can you please elaborate on it? I don't see how this problem can be reduced to a knapsack. An essential property of a knapsack is its limited capacity, isn't it?

[abhimanipal]

I guess the terminating condition could be when all the fruits are un reachable( height wise) ....

[Slobodino]

Here is the updated code, it still doesn't deliver the expected results. Can't say what's wrong with it, most of the times it seems to return the maximum weight of one fruit as opposed to the maximum weight I am able to pick up.

#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;
}

And here's some input:

3 100 10
93 90
84 300
83 500

should return 590 (=90+500), however it returns 500

6 100 10
91 90
82 300
83 500
74 1000
75 2000
76 4000

should return 7000 (=4000+2000+1000), instead it gives 4000

8 100 10
91 90
82 300
83 90
74 500
75 90
76 90
65 20000
64 10000

should return 30800 (=300+500+20000+10000), it returns 20000

[Adak]

The answer to the problem is to use minimax to select the best sequence (or alpha-beta if you prefer), and depth first search. Then you can find absolutely the best picking sequence, for any arrangement of fruit and heights.

Dynamic, shallow algorithms will generally approximate, but can't give, the best sequence, all the time.

[craig_ka]

Sorry about taking you on a tour of the close but incorrect solution. When first reading the problem statement of maximizing weight for a given height the idea of a knapsack popped in my head and I never thought to look at how the algorithm would work on actual input. But now looking at the input and looking through the data generated I can see that it won't work in this situation.