Java – what algorithm is this? Box packaging / backpack?

I was working on an application last night and encountered a special problem. I'm sure I may have an effective algorithm to solve it Who has a suggestion?

Question:

TL; Dr: maybe pictures will help: http://www.custom-foam-inserts.com/. I have many items suitable for various compartments: I want to minimize the number of boxes to take

.

I have a set of N expensive electronic equipment. I want to put it in a specially designed protective box Each of these boxes has many compartments, and each compartment can be equipped with an item: some are specially designed to fit specific items (i.e. camera shaped holes), and some are universal (rectangular holes) I know in advance that there are different sizes of C compartments and sizes

These boxes have two different layouts, each with at least one compartment The layout may be "two large rectangular compartments and four small circular compartments"

Each compartment size exists in at least one layout, but my item does not fit any compartment size Each item is suitable for at least one compartment and can be put into multiple different compartments: for example, my DSLR camera may fit tightly in the "medium Rectangle" compartment, loosely in the "large rectangle" and perfectly in the "SLR camera compartment", but it is not suitable for the "small circle" To this end, I listed which compartments are suitable for each project

These items are moderately heterogeneous – for example, there may be 50 items of one size and 20 items of another size

Each box has two costs volume and dollars (but d ~ is proportional to V) I need to minimize one or two of these costs and put all my items in the box at the same time Due to the layout of the box, the best solution may include unused compartments If both solutions have the same volume, select the solution with the most unused compartments Because each compartment exists on at least one layout and each item is suitable for at least one compartment, there is always a solution for all items

Number of projects: < = 2000, average 150 Number of compartments: < = 1000 Number of layouts: < = 1000 Any ideas about this? I looked at knapsack and bin packing algorithms. I'm not sure if they are feasible Thank you.

Solution

From the description of the problem, it really seems to be a knapsack problem, because you must maximize your available space and remember the weight of the options

Depending on what you use, you can also consider using genetic algorithm Since this problem is NP complete, if you need to add more projects, the running time will eventually explode. Therefore, if I need the best solution available, I will mainly use the time required for this problem

On the other hand, genetic algorithm should be able to provide some solutions in a relatively short time. However, the solutions it provides may not be as good as those provided by knapsack algorithm, so I will choose GA. if I have time constraints, I need to provide some solutions, I don't care whether it is absolutely the best