0

Ok, the example doesn't matter. I was just using it to put it in context. But basically i am wondering how to take a random value from an array/arraylist?

I tried using this: int random = (int)input[Math.floor(Math.random() * input.length)]; but it highlights potential loss of precision even though i've already cast it. Have i cast it wrong?

The example is irrelevant really and i do accept answers to all my questions. Initially i wanted to see a correct answer without influence from me to see if i was on the right track.

binary101
  • 1,013
  • 3
  • 23
  • 34
  • 1
    The problem is fairly straight forward. I suggest you try to write a program which loads/defines the array/list of data, and then follows the algo you suggest until you get stuck or it doesn't work and ask a more specific question. – Peter Lawrey Nov 29 '12 at 11:41
  • 1
    [exact duplicate](http://stackoverflow.com/questions/13613373/java-batching-integers) of your own question. – jlordo Nov 29 '12 at 11:49

1 Answers1

1

This is exactly the bin packing problem. It is also NP-Complete, and thus there is no known polynomial solution (and the general assumption is one does not exist, but it is not proven yet).

The problem is widely studied if you are looking for approximation algorithm, or a relatively efficient exact algorithm

PS - the random approach you suggest will get you a solution, but it won't be OPTIMAL.
Counter example:

arr = [2,3,4,1] , size=5

A possible solution to your algorithm could be: select 3, select 1, select 4, select 2, which will yield:

[3,1],[4],[2]

While the optimal solution will be [3,2],[4,1]

(-) I believe a greedy approach (chose the highest, put it in an available bin - if it fits, and if it doesn't - "open" a new bin) will do better then the randomized solution but will still be not optimal, with the counter example: 

arr = [5,4,4,3,2,2] size = 10

greedy will yield [5,4],[4,3,2],[2] while optimal is [5,3,2],[4,4,2]

Regarding the loss pf precision - it happens because Math.floor(double) yields a long, while you use it as an int (and you might theoretically lose data when doing so). However, it is not a problem in your case since Math.floor(Math.random() * input.length is guaranteed to be in the range of an int because input.length is an int and Math.random() < 1.

amit
  • 175,853
  • 27
  • 231
  • 333