I'm trying to solve some coding problems and I came across this problem:
As electricity prices soar, there must be a way to reduce waste by increasing the use of heavy-duty machines, such as elevators. We formulate the problem as follows. There is $ N $ people $ (p_1, …, p_N) $ wait in a queue to enter an elevator. By the way, there is only one elevator that connects the ground floor to the sky (that is, there are no other stops in between). In addition, everyone is waiting on the ground floor. Just for simplicity, we are concerned only with the use of the elevator's ground-sky path. Each person $ p_i $ has a positive weight wi. The weight capacity of the elevator is $ M $. Therefore, not all people can be transported together. They are transported in several trips. Each person enters the elevator according to his order in the queue. Meaning, $ p_1 $ enter first, then $ p_2 $ etc. Suppose at $ t-th $ travel, people $ p_j $ through $ p_k $ enters the elevator. The loss factor (WF) of trip t is defined as
Your task is to minimize total waste (TW), defined as:
Or $ S $ is the total number of trips required to transport everyone from the ground to the sky. Note that the WF of the last trip is not included in the TW calculation.
I found myself completely stuck here, I thought it could be solved via DP but I do not know how. Especially with the condition of maintaining order.
The complete problem can be found here Problem K: Increase the use!