Minimum rearrangment of boxes to accomodate new box in cartons

Правка en1, от harshaga97, 2018-04-11 14:15:07

There are n cartons. Each carton can have some boxes in it. Each box occupies some space.

We are given the free space left in each carton and the list of sizes of boxes in each carton. There is no restriction on number/size of boxes in each carton.

Now we have a new box, with size x, which needs to be accomodated in any one of the cartons. Rearrangement of any number of boxes from a carton to any other carton is allowed, provided the new carton has the space left to accomodate the rearranged box.

I need to find the rearrangement that can be obtained in the least number of box movements & can accomodate the new box.

I am more interested in the case that the new box cannot be accomodated in any free-space of any carton and some rearrangement is mandatory to make room for the new box.

Input format
x : size of new box
n : no of cartons
    box_no_1 :: free_space, no_of_boxes, box1_size, box2_size, ...
    box_no_2 :: free_space, no_of_boxes, box1_size, box2_size, ...

example:
x : 60
n : 3
    1 :: 10 , 3, 10 , 10 , 30
    2 :: 20 , 2, 20 , 10
    3 :: 50, 3, 10, 30, 20

Answer:: box with size 10 in carton 3 can be moved to carton 1. Then new box can then be kept in box 3.

Can someone tell me how to solve this problem ?

Теги integer optimization, greedy, dynamic-programming, #algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский harshaga97 2018-04-11 19:42:15 172
en1 Английский harshaga97 2018-04-11 14:15:07 1377 Initial revision (published)