How to prove this greedy approach in this problem

user_13641125 0
Viewed 47

according to https://cses.fi/problemset/task/1085

the simplest method to partition the array is to start from left to right and as long as if you can add the current number to the subset and it's not surpass the maximum value ( find this value by binary search it ) then add it to the current subset. otherwise just start a new subset and do the same thing all over again

Ex. 2 , 4 , 7 , 3 ,5 and the maximum value is 8 using the method above you will have [2,4] , [7] , [3,5]

i understand that this greedy method works. but the question is how can you prove this approach mathemetically ??

and if i find some greedy related problem like this again should i try to prove it or it doesn't need to prove every single greedy problem ?

PS. sorry for confusing language. i hope you understand what i was trying to convey.

greedy math algorithm
1 Answers

There are two parts to this solution: the binary search and the greedy partition. Binary search is not a greedy algorithm, it relies on sorted values of a function.

For the binary search, we know that if it's possible to reach a maximum sum s of all the parts in the partition of k parts, we necessarily can reach the same or lower maximum sum by splitting one of the parts that has that maximum sum (the resulting maximum will be lower if and only if that part was the only one holding the maximum).

So the values of s above, given the input k, are sorted -- they descend monotonically as k increases, which means we can binary search on them.

About the greedy accumulation when partitioning with target maximum s, we can say that if we still are able to add to a part and stay below s + 1, we guarantee that at least one part ahead in the partition would have a smaller sum than if we did not add the value. Adding the value doesn't guarantee that we can reach the target s and k in this particular partition attempt, but not adding it means we would not have done our best to keep all the sums as small as possible, which violates our intention.

user_20347870
Related