Optimisation problem

Revision en2, by 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

Tags #dynamic-programming, #optimization, #array


  Rev. Lang. By When Δ Comment
en2 English harsh-apcr 2024-03-31 21:48:47 138
en1 English harsh-apcr 2024-03-31 19:59:32 390 Initial revision (published)