harshaga97's blog

By harshaga97, history, 12 months ago, In English,

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, ...

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.

An idea is to use bin-packing algorithm to solve this. But bin-packing does not involve rearrangements.

Any ideas on how can bin-packing or any other technique be moulded to solve this?

Read more »

  • Vote: I like it  
  • -5
  • Vote: I do not like it