1

I have any number of graphs. Each graph is a plot of points, not necessarily an equation.

I need to pick a point on each graph in way that the following is true:

  1. The sum of the y values of each point is maximized
  2. The sum of the x values of each point does not exceed a limit L, which can be any positive number.

The problem seems so simple, and yet I cannot find a way to solve the problem mathematically. There are several ways to solve the problem using CS, but I would prefer to avoid those if possible.

Mike Pierce
  • 18,938
user3144349
  • 11
  • Welcome to Math.SE! Could you expand on the methods you know from CS that are relevant here? That might help people to get started on other solutions. – Hrodelbert Jun 02 '15 at 18:41
  • Thanks! And there are really 2 ways to go about it. One of which was already described below by @Ross Millikan, which is the fastest way to do the problem. The other way is to eliminate all points that could never be optimal, IE (4, 4) could never be better than (2, 5), and then iterate over every possibility. – user3144349 Jun 02 '15 at 19:05

1 Answers1

1

This has the combinatoric feel that says to me finding a perfect algorithm will be hard and the problem may even be NP hard. I would suggest the following reasonably greedy algorithm:

  1. Find the maximum $y$ value in each graph
  2. Add up the corresponding $x$ values. If the sum is less than $L$ you are done.
  3. If the sum is greater than $L$, look over the next best $y$s that are at lower $x$s than the ones you are using. Find the one that maximizes the ratio $\frac {\Delta x}{\Delta y}$ Replace the applicable point in your list.
  4. If the sum of $x$s is less than $L$ you are done. Otherwise repeat step $3$

This is not guaranteed to find an optimal solution. It could be that the third best $y$ in one graph comes with a very small $x$ and would get the sum down to $L$ in one go.

Ross Millikan
  • 374,822
  • 1
    Thanks for the answer! I've actually already tried this, and it works well for the most part but can result in some highly inaccurate results, depending on the input data. – user3144349 Jun 02 '15 at 19:06