Help with homework

help
, ,
1

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
2

Is there a online version, to be able to test it myself ?

1 Like
3

@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 :slight_smile:

4

I hope this helps - http://en.wikipedia.org/wiki/Knapsack_problem

1 Like
5

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?

6

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.

7

@betlista: but the problem is find k as small as possible?

8

this is handled by “want to be as close to M as possible”

9

@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…

10

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.

11

Ok, I understood, thank you so much @betlista :slight_smile:

12

@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.

  1. 2+3+8
    ,10,9,5

  2. 8+5,10+3,9+2 (This being answer)

3 Likes
13

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
14

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) :slight_smile: @betlista @baljitsingh

15

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…

16

@betlista can you please explain me the complexity part.how do we get O(M*N).
i can think of O(N^2).

17

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)?

18

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).