I have a homework but I can’t have any ideas to solve it.
The problems can be can be described:
Having an array with n elements. Your task is dividing array into k group, and sum of all integer in group must not be larger than M, k is smallest as possible. And you can choose integers which are not continous.
Example: with test:
8 14
9 7 4 3 3 2 8 6.
(n=8, M = 14, a[] = {9,7,4,3,3,2,8,6}
and result is: k = 3.
Explanation: We choose there group: (1,4,6) (7,8) (2,3,5) – the position.
Limitation: n<=100; M,a[i] <= 10^4.
1 Like
Is there a online version, to be able to test it myself ?
1 Like
@betlista: My teacher had created a topic, and today he gave me that problem. I have to find the solution to solve it, and prove that solution is true
Your idea for that problem is finding the longest subarray that sum of all elements is not larger than M, then marked them and continue to find another subarray, right? @betlista?
The length is not important, you just want to be as close to M as possible. Once you have a group you continue the process again.
@betlista: but the problem is find k as small as possible?
this is handled by “want to be as close to M as possible”
@betlista: Can you prove for me that if we choose a subarray that sum of all elements is nearest to M, and then we continue the process, we will have an k group, and k is smallest? I think it will be heuristic algorithm…
Isn’t it obvious? You have S (sum of all a_{i}) and you are subtracting value m in each step (m <= M). While m is always maximal possible, the number of subtractions is minimal possible.
Ok, I understood, thank you so much @betlista
@betlista . I still cant figure out how would above method ensure smallest value of k possible?
for input
6 13
2 3 5 8 9 10
now there can be 2 answers according to your approach.

2+3+8
,10,9,5

8+5,10+3,9+2 (This being answer)
3 Likes
Ok, and if you sort the array in decreasing order and you use the biggest unused item first?
10 9 8 5 3 2 > 10+3, 9+2, 8+5
2 Likes
And I think that the final algorithm is : Sort the array in decreasing order, with an unused item, we find the subarray that sum of all elements as close as M and marked it, and try to process another unused items utils all are marked. Complexity is O(n^2) @betlista @baljitsingh
I’d say complexity is more like O(K*M*N), this pseudo polynomial algorithm is O(M*N) and one have to run it K times…
@betlista can you please explain me the complexity part.how do we get O(M*N).
i can think of O(N^2).
This max is calculated by dynamic programming which is O(N*M), but I mentioned this above, can you share how to do that in O(N*N)?
okay now i understood how to do it in O(N*M) using dynamic programming.
I was thinking about some wrong approach(it dosen’t works).