i'm not sure "permutation" right word, scenario have list of ~40 objects. each different object has different value , cost.
say objects contain value between 1 , 5. trying combine list of objects exceed given targetvalue, find combination lowest total cost, , return combination. combination potentially contain many duplicates of 1 of objects in list.
for example, if list of objects { a, b, c, d }; output could { a, a, a, a, a, a, a, a, a, }. however, note order matters. { a, a, b } may have different total value { a, b, }
currently, i've been trying brute force solution. however, 40! combinations, running out of memory while keeping track of different "permutations".
i still prefer run through every combination accuracy, increased time perform calculation not problem, said before, biggest problem memory.
current code: (incompletelist starts beginning object)
while (incompletelist.size() > 0) { container container = incompletelist.get(0); (myobject o : objectlist) { container newadditioncontainer = new container(container);//copies list of objects new container newadditioncontainer.addmyobject(o); if (newadditioncontainer.gettotalvalue()) < targetvalue) { incompletelist.add(newadditioncontainer); } else { completelist.add(newadditioncontainer); } } incompletelist.remove(container); } //code loops through completelist , grabs container cheapest cost, //but in actuality code hasn't been able run yet. i'm pretty sure above work, if able complete (but cant due memory); how can change algorithm try , lowest cost , stay within memory limits?
build permiterator intialized list of objects , desired permutation length. iterate iterator beginning length 1 until complete iteration same length permutations exceed desired value. store actual permutation , current best permutation, exceeds desired value , has lowest cost, independent of permutation length. way avoid storing permutations in lists , going out of memory. 40 objects can still take quite long.
Comments
Post a Comment