Have a batch of goods need to transport charter, [110] 100 is weight, 80 is the volume, assuming that charged according to weight, there are models of N, the weight of the vehicles to transport volume is (X, Y), the car freight=X * (shipping fee + unloading fee) + delivery cost, same models can be repeated, for freight the least charter plan (add up all the models, the weight of the volume is greater than the weight of the cargo volume),

For example, the current order [110] need to transport, are known models A [10, 20] A loading charge, discharge fee is 20, 30, respectively take delivery cost 30, model B (20, 30), B loading charge, discharge fee is 15, 30, respectively take delivery fee 45, freight at least is 5 * A * B + 1, cost=5 * * 20 (15 + 30) + 45 + 5 * 1 * 10 * (20 + 30) + 1 * 30=5255


Which not only two models can be N, if meet the weight, but volume does not meet the need of extra buses, add the new car freight only need to pick up the goods, the X * (shipping fee + unloading fee)=0

Now know, greedy, dynamic programming can not meet this requirement, if use deep search, will be very time consuming, I use recursion can traverse, but performance is very poor, do not know to have bosses know other algorithm can solve this problem

CodePudding user response:

The key problem is to meet at the same time the volume and weight, but the cost only to weight multiplied by (shipping fee + unloading fee), equivalent to the cost of a car is not fixed,
And in order to satisfy the volume weight, meet the weight 5 car in front, behind the new car is just in order to satisfy the volume, freight don't need the loading + unloading charge, as long as you take delivery fee