3
$\begingroup$

I thought of this question while portioning chicken in the sandwich shop where I used to work. It may reduce to the bin-packing problem, but I am not certain. It is as follows:

You have been given a bucket of irregularly cut chicken to portion for sandwiches. You have been told that each portion must be 3.1 oz. You have used a scale and measured each piece to within 0.1 oz. So for example maybe you have a 1.1 oz piece, and a 0.7 oz piece, and a 2.3 oz piece, etc. Consider these masses to be good, known integer multiples of 0.1 oz. So you have done this and you have made a big list of all your chicken sizes (you are a very diligent employee).

Here is the question: is there any quick way to look at your list and know whether or not there is a way to portion the chicken faster than just trying every combination? You have 31 lb of chicken to portion, and there must still be living people to serve chicken sandwiches to when you are done!

Note that (in some contradiction to my last comment) you don't need to know how to portion the chicken. You just need to know if it can be done. For example, if you were given two 3.0 oz pieces and one 0.2 oz piece, you would know the total is divisible by 3.1, but you could not make two packets out of it.

Thanks, GOT

$\endgroup$

migrated from mathoverflow.net Jul 20 at 2:19

This question came from our site for professional mathematicians.

1
$\begingroup$

This is not a complete answer, nor optimal, nor from a specialist. But I would like to explain what I think could be a reasonably good approach. Note that it is a constructive approach, still in the style "try out many combinations", just more efficient than a random approach. I do not know whether there is an approach that just gives you a fast yes/no answer without telling you the actual combinations.

1) Order the pieces by weight. I assume that they are all 3.1 oz or less and that you cannot cut them into smaller pieces.

2) Look for 3.1 oz pieces and put them aside (or into a sandwich).

3) Look at the biggest piece left and look for complementary pieces (of weight 3.1-x), starting from the bottom of the ordered list, and going up only until the sum is still smaller or equal than 3.1 oz. If you find a complementary piece, put them both aside. Do the same for all other pieces (of course, if you have many pieces with the same weight, you can skip the remaining ones as soon as you have a failed attempt), always starting the check for the complementary piece from the obvious place in the list (i.e.: start to look for complementary pieces from the same place in the list where you found the last successful match: smaller pieces won't do).

4) Then start again from the first piece and look for fillings with three pieces. If you have stored the information about the available sums of weights of pairs of pieces in the previous round, without repetition (but with a link to the actual pairs), and filtered out the pairs were some pieces have already been put to the side, you might be able to exploit this information to be faster: you are again looking at pairs of data, not at triples!

5) Do it again and again, always increasing the number of pieces you consider, but always comparing only the weights of single pieces with the available sums of $n-1$ weights smaller than 3.1 oz (which you have stored in the previous round)

How do you know when to stop? Well, naively, you cannot use more than 31 pieces for a sandwich. But, more efficiently, when at the beginning of a round you start comparing the biggest piece left with the smallest sum of $n-1$ weights, you can stop if the total sum is bigger than 3.1 oz.

Sorry if the explanation is not very clear. I can write down an example, if you want. Again, this is a naive way to optimize, based on ordering (so as not to check things many times) and storing data (for the same reason). I am not claiming that this is optimal, but it might be a relatively good solution. It should be doable by hand and if you know some programming and have a laptop at work, you can probably use this algorithm to get all the combinations explicitly computed in a couple of seconds.

Remark: I think that it can be shown that this greedy approach actually gives you the highest number of doable sandwiches, because at the end you are left only with small pieces, and you could not do anything meaningful with them anyway, even if they were combined into bigger pieces of the same total mass.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.