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
@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
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 sub-array that sum of all elements is not larger than M, then marked them and continue to find another sub-array, 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 sub-array 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 ai) 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
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 sub-array 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).