I have no idea if this is the right place to ask a question like this. As I searched if it was, I couldn't get the answer. If not, please remind me and I will delete this. I have a specific problem that I can't solve. Please suggest solutions if possible. The problem goes like:

We have n1 boxes of 50kg and n2 boxes of 100kg cargo. We have a plane which contains at most k kg. We have to ship all the cargo from one mountain to another. The principle of shipping is that at any given time (from 1 mountain to 2 or vice versa) there should be at least 1 cargo on the plane. The question is, how many ways are there to ship all the cargo in minimum number of shippings. (Like if the minimum number of flights required to ship is 5, then question is how many ways are there to ship all the cargo in 5 flights). A way is considered different if at least one flight had different amount of boxes.

I'm guessing that graph traversal should be used. Tell me if I'm wrong.

  • $\begingroup$ Do I read tha tcorrectly? You have to bring some cargo back from 2 to 1 even if your overgoal goal is to go from 1 to 2? (So a bit as in the wolf/goat/cabbage problem)? $\endgroup$ – Hagen von Eitzen Apr 8 '18 at 10:38
  • $\begingroup$ I'd return with a small box each time. $\endgroup$ – William Elliot Apr 8 '18 at 10:42
  • $\begingroup$ @HagenvonEitzen yup. It's weird $\endgroup$ – George Tsertsvadze Apr 8 '18 at 10:45
  • $\begingroup$ @WilliamElliot and that's exactly the issue. You may get the same number (minimum number) of crossings even if you bring the big box. And you have to compute number of all the ways with minimum crossings. $\endgroup$ – George Tsertsvadze Apr 8 '18 at 10:46
  • $\begingroup$ The less gou bring back, ths less you'll have to ship twice.z@GeorgeTsertsvadze $\endgroup$ – William Elliot Apr 8 '18 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.