Space (slots) optimization algorithm

Question

I'll start right with an example:

The game has a bag that players will use to store their items (items have variable sizes), and the bag also has a variable size.

In the bag of 8x15 slots I need to insert an element that occupies 2x2 slots, I can find the space to check if there is enough space to store this element - this is easy, but what if I don’t put on, t there is enough space to store the requested element? This is a real problem.

I am trying to find a way to actually rearrange all the current items in the current bag to make room for the new item.

Is there any algorithm that will help me do this?

EDIT

Rules:

• I cannot delete any of the current items in the bag, just rearrange them to save a new one if there is not enough space.

Answer 1

I think this is unfortunately NP-hard problem, but you can use the greedy approximation algorithm. The approximation algorithm can work as follows:

• Sort all goods by volume of goods, descending.
• Iterate through the list and try to place the current item anywhere
• If at any time the current item cannot be set anywhere, decide that the item cannot be raised.
• If all parts are installed, decide that the item can be lifted.

This is based on the intuitive idea that larger pieces are “harder” to place than smaller ones. Another thing you could do if most of the elements are 1x1 is a brute force solution, which is quite possible in such a small inventory. This will work as follows:

• Try each position for the current part, where it still fits and for each such position:
• Do this with the next untethered part.

This will always solve your problem, but will be slower (albeit more accurately). This algorithm can be improved, leaving each 1x1 piece, placing them subsequently.