I have an optimization problem which I currently solved by brute force but I was wondering if there is a more efficient solution. I wasn't able to reduce the problem to some well known problem in dynammic programming or find some similar problem.
Problem:
| I | 1 | 2 | 3 | 4 | ... |
|---|---|---|---|---|---|
| x | 100 | 200 | 150 | 400 | ... |
| y | 50 | 300 | 150 | 100 | ... |
| z | 50 | 100 | 50 | 120 | ... |
$$V = argmax_{S \in I}(1 - \frac{\sum_{i \in S}y_i}{\sum_{i \in S}x_i}) * \sum_{i \in S}z_i$$ $$x \in R^+ \cup \{0\}$$ $$y \in R^+ \cup \{0\}$$ $$z \in R^+ \cup \{0\}$$
So the task is to find $S$ (a subset of $I$) so $V$ is maximized.
To extend this problem there are restriction on $S$. $S$ can consist only of consecutive elements of $I$ with maximum of one gap. So for example $S = {2,3,6,7,8}$.
Further extension is that there are restriction on $(1 - \frac{\sum_{i \in S}y_i}{\sum_{i \in S}x_i})$ which has to be greater than a constant $c$. $$(1 - \frac{\sum_{i \in S}y_i}{\sum_{i \in S}x_i})>c$$
P.S.: Who is interested how this problem popped up. This optimization problem is the payout of the austrian governmental corona business support "Fixkostenzuschuss 800.000" where x are the sales of 2019 and y the sales of 2020 and z the fixed costs.