Optimisation problem

Правка en2, от harsh-apcr, 2024-03-31 21:48:47

Given two arrays of integers $$$x$$$ and $$$y$$$, of length $$$n$$$, find a partition of indices $$${1, \ldots, n}$$$ such that you minimise the score, where the score of a partition $$$S_1, S_2$$$ is defined as $$$\max(\sum \limits_{j \in S_1} x[j], \sum \limits_{j \in S_2} y[j])$$$

just find the minimum score that can be achieved, I fancy a dp approach, any help is appreciated, thanks

EDIT : assume the sums of $$$x$$$ and $$$y$$$ are bounded above by $$$M$$$, then a solution with time complexity parametrised by $$$M$$$ might be good

Теги #dynamic-programming, #optimization, #array

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский harsh-apcr 2024-03-31 21:48:47 138
en1 Английский harsh-apcr 2024-03-31 19:59:32 390 Initial revision (published)