Description of the problem

There are many "objects" (in the example there are two, but in practice several thousand)

each object has states (in the example there will be 3 in practice ~ 50)

each state is characterized by two indicators ( п and р )

it is necessary to select a set of states in which the сумма(п) and сумма(р) at least a certain number X.

Example

 +--------+----+------+------+----+--------+--------+ | Объект | п0 | п1 | п2 | р0 | р1 | р2 | +--------+----+------+------+----+--------+--------+ | 1 | 0 | 1000 | 1500 | 0 | 100000 | 102000 | | 2 | 0 | 1000 | 2000 | 0 | 2000 | 2500 | +--------+----+------+------+----+--------+--------+

With a minimum amount of 102,000

In this example, it is seen that the optimal is the set of states (2,0) сумма(п) with = 1500

Attempts

1) Earlier, I considered the optimal state (ratio р\п ) for each object, then sorted according to efficiency and chose an amount not less than the limit.

- The given example showed that the result does not provide maximum efficiency.

2) I thought about simple brute force — it works very slowly with a 2000 * 50 matrix size

3) I thought to calculate the x-best state for each object (the first, second, and so on, the best)

and then, by analogy with the first option, after choosing the best one, compare the second best with the first best and replace if efficiency increases.

- I do not know how to formulate it correctly and how to stop so as not to go through all the options.

I would like to see ideas as best as possible to solve this problem. (time is important, but + - the hour does not solve anything)

A solution option in R or vba would be perfect.

PS

states have the following properties:

1) р(i)=f(п(i)) - p depends on n, but the dependence is not known.

2) p(0)=0 п(0)=0 - at zero n and p == 0

3) п(i+1)>п(i) - n grows as the state number increases

4) p(i+1)>=p(i) - p does not decrease with an increase in the state number (increase in n)

  • Should total efficiency be maximized for each object independently? Or should this efficiency be maximized for all objects? What to do if for different objects the maximum efficiency is achieved with a different combination of states? - hedgehogues
  • @hedgehogues Added answers, I hope it became clearer. - Batanichek
  • I understand the problem correctly, that formally, you need to make 2000 * 50 divisions and find the maximum? - KoVadim
  • @KoVadim matrix 2000 * 50 are state objects *, that is, you need to choose a vector of 2000 size (where each digit is the state number for each object) so that the efficiency calculated for this vector is maximum. that is, if you solve by enumeration (in the forehead), then in the indicated example (2 * 3) you need to iterate the states (Object1, Object2): (0,0); (0,1); (1,0); (0,2) ; (2,0); (1,1); (1,2); (2,1); (2,2) for each, calculate the efficiency as the sum (p) / sum (p) and choose the best set. - Batanichek
  • one
    This is very similar to the task of packing a backpack. But you need to think more deeply. - KoVadim pm

0