-
Dec 18th, 2013, 04:20 PM
#1
Thread Starter
Fanatic Member
Calc boxes count and boxes positions problem
Hello,
I've came across of a idea while watching tv, that turned into a problem.
I'm trying to figure how many boxes can fit inside a bigger box. This should be easy calculating areas, but thing is, some boxes should not be able to be piled on each other due to weight or something.
Container box has lets say 100x100x100;
Then I'd have 2 boxes with 20x20x20, 2 boxes with 10x20x20, 3 with 30x30x30 and 1 that must be on top or just alone with 50x50x20
how one earth should i be able to calc such a thing? Yes I know, bad tv show for sure.
thanks
-
Dec 18th, 2013, 04:43 PM
#2
Re: Calc boxes count and boxes positions problem
Don't think you'll get very far calculating areas!
Your example is frankly very poor. The capacity of the big box so far exceeds that of the smaller boxes combined that only mind-bending incompetence would make it impossible to get the lot in! There is no general algorithm here. A brute force search is going to be your only option, especially if you are permitted to rotate the boxes.
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Dec 18th, 2013, 05:13 PM
#3
Thread Starter
Fanatic Member
Re: Calc boxes count and boxes positions problem
Naa, there is no error, that's actually on purpose. I should be able to find the best possibility of leaving the least number of boxes out of the container (in case they were more then the max capacity) Else, if the space of the container exceeds the sum of the total boxes, it should not waste space and leave space for new boxes.
I know my example is poor, problem is, I don't know how to explain it better. This should be the same idea on ship containers organization, using a 3D matrix to organize cargo.
A bunch of cycles were my idea at start but i thought there was an other way, a better way.
-
Dec 18th, 2013, 05:35 PM
#4
Re: Calc boxes count and boxes positions problem
Ship containers are a standard size precisely to get around this problem. You build your ship around the number of containers you want it to carry not the other way round. And in the real world that's pretty much the model for all packaging. You pile your product into as neat a pile as possible and then order bespoke boxes. As soon as you get into carriage of items of varying sizes there is nothing but packer's experience to guide you. Whilst a computer may reach a more 'perfect' answer there is no efficient way of reaching that answer which obviates the need for 'experiment' (trial and error (brute force and ignorance!))
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Dec 18th, 2013, 05:41 PM
#5
Re: Calc boxes count and boxes positions problem
However, this problem is not nearly as simple as you think it is. It falls into the general category of problems including the Knapsack Problem:
http://en.wikipedia.org/wiki/Knapsack_problem
Pay particular attention to this line:
The decision problem form of the knapsack problem (Can a value of at least V be achieved without exceeding the weight W?) is NP-complete, thus there is no possible algorithm both correct and fast (polynomial-time) on all cases, unless P=NP.
That bit about "no possible algorithm both correct and fast" is the key point. It may seem simple, but it is only simple if you make the bounds of the possible solution set sufficiently small that testing all possible combinations is fast.
My usual boring signature: Nothing
-
Dec 18th, 2013, 06:01 PM
#6
Thread Starter
Fanatic Member
Re: Calc boxes count and boxes positions problem
By the way, i did forget the margins between boxes, plus there are other variables, such as in case there was the need of a second container, shouldn't the boxes be reorganized for best accommodation and not leaving one container too full and an other too empty.
This problem isn't any simple.
-
Dec 18th, 2013, 10:14 PM
#7
Re: Calc boxes count and boxes positions problem
Ya! Not simple at all. I have solved this type of problem before using a genetic algorithm. That's not even close to being a simple solution. I think it's over in the .NET CodeBank, but it wasn't a solution to this problem, but another problem in the same category of problems.
My usual boring signature: Nothing
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|