algorithm - C++: Finding all combinations of array items divisable to two groups -

i believe more of algorithmic question want in c++. let me illustrate question example.

suppose have n number of objects (not programming objects), each different weights. , have 2 vehicles carry them. vehicles big enough carry objects each. these 2 vehicles have own mileage , different levels of fuel in tank. , mileage depends on weight carries.

the objective bring these n objects far possible. need distribute n objects in way between 2 vehicles. note not need bring them 'same' distance, rather far possible. example, want 2 vehicles go 5km , 6 km, rather 1 going 2km , other going 7km.

i cannot think of theoretical closed-form calculation determine weights loaded in each vehicle. because remember need carry n objects fixed value.

so far can think, need try combinations.

could advice of efficient algorithm try combinations?

for example have following:

int weights[5] = {1,4,2,7,5}; // can more values 5 float vehicelonemileage(int totalweight); float vehicletwomileage(int totalweight); 

how efficiently try combinations of weights[] 2 functions?

thw 2 functions can assumed linear functions. i.e. return value of 2 mileage functions linear functions (different) negative slopes , (different) offsets.

so need find like:

max(min(vehicleonemileage(x), vehicletwomileage(sum(weights) - x))); 

thank you.

• this should on cs or math site.
• simplification: instead of array of objects, let's can distribute weight linearly.

the function want optimize minimum of both travel distances. finding maximum of minimum same finding maximum of product (without proof. see this, think of relationship between perimeter , area of rectangles. rectangle biggest area given perimeter square, happens have largest minimum side length).

in following, scale sum of weights 1. so, distribution (0.7, 0.3) means 70% of weights loaded on vehicle 1. let's call load of vehicle 1 x , load of vehicle 1-x.

given 2 linear functions f = x + b , g = c x + d, f mileage of vehicle 1 when loaded weight x, , g same vehicle 2, want maximize

(a*x+b)*(c*(1-x)+d) 

let's ask wolfram alpha hard work us: www.wolframalpha.com/input/?i=derive+%28%28a*x%2bb%29*%28c*%281-x%29%2bd%29%29

it tells there extremum @

x_opt = (a * c + * d - b * c) / (2 * * c) 

that's need solve problem efficiently.

the complete algorithm:

• find a, b, c, d

  b = vehicleonemileage(0)

  a = (vehicleonemileage(1) - b) * sum_of_all_weights

  same c , d

• calculate x_opt above.

  • if x_opt < 0, load weight onto vehicle 2
  • if x_opt > 1, load weight onto vehicle 1
  • else, try load tgt_load = x_opt*sum_of_all_weights onto vehicle 1, rest onto vehicle 2.

• the rest knapsack problem. see http://en.wikipedia.org/wiki/knapsack_problem#0.2f1_knapsack_problem

  how apply this? use dynamic programming algorithm described there twice.

  • for maximizing load tgt_load
  • for maximizing load (sum_of_all_weights - tgt_load)

• the first one, if loaded onto vehicle one, gives distribution less expected on vehicle one.

• the second one, if loaded onto vehicle two, gives distribution more expected on vehicle two.
• one of best solution. compare them , use better one.

i leave c++ part you. ;-)