Partitioning a whole number in a particular way

[robertjordan]

Hi,

Let W be the sum of all the people's weights, let P be the total number of pizza slices available.

If:

• I have P slices of pizza (P<=W)
• I have n people I want to split the pizza with
• I want to use people's weight to determine how many slices they get (more weight -> more slices)
• I don't want to split any slices. (I want to leave all slices whole)
• A person cannot eat more slices than the value of their weight. (a_i<=w_i)

If w₁, w₂, ... , w_n are the weights of the n people, and a₁, a₂, ... , a_n are the numbers of slices each of the n people get (where each a_i is a whole number >= 0), I want to find the set {a₁, ... , a_n} such that:

∑ⁿ_{i = 1}| a_i/P - w_i/W |

is minimized.

Is there a formula (some uses of ceiling, floor?) or algorithm to find this set {a₁, ... , a_n} ?

 

[PeroK]

Hi,

If:

• I have P slices of pizza
• I have n people I want to split the pizza with
• I want to use people's weight to determine how many slices they get
• I don't want to split any slices. (I want to leave all slices whole)

How can I decide how many slices to give each person? I know some people may end up with 0 pieces, but that's okay.

You could give all P slices to the heaviest person. Or, to the lightest.

 

[kuruman]

In order to decide how to distribute the slices you need a more quantitative rule (or set of rules) than just "To use people's weight". Use people's weight how? For example, does a heavy, apparently well fed person get more pieces than a skinny, emaciated person or the other way around? What criteria must be met for a person to get at least one piece? And so on.

Of course you can always rely on probability. You can have the people toss coins and get a slice every time they get heads. You assign progressively fewer coin tosses to the people you think should get fewer slices following whatever weight criterion you have.

 

[Dale]

Shouldn’t you just take $w_i/W$ and round to the nearest 1/P

 

[kuruman]

Shouldn’t you just take $w_i/W$ and round to the nearest 1/P

It depends on one's particular weighting philosophy. I tried some examples using $(w_i/W)^n$. Positive values of $n$ favor the heavy people while negative values favor the skinny people. One can also try exponentials a la partition function, I guess.

 

[robertjordan]

Shouldn’t you just take $w_i/W$ and round to the nearest 1/P

Thanks for the replies.
I don't mind so much favoring someone more than others as long as:

• (a_i<=w_i) is not violated
• we assign exactly P pieces of pizza. no more, no less
• only whole slices can be assigned (no fractions for a_i)

For example, if we have

w₁ = 25
w₂ = 9
W = 34
P = 17

Then ROUND(P*w₁/W) = 13
and ROUND(P*w₂/W) = 5

Which means we've just assigned 18 pieces of pizza but we only have 17.I'm trying to find an algorithm that can ensure we give out exactly the P pieces and we also don't violate (a_i<=w_i).

 

[Dale]

Don’t round up. Round off. It should work unless you get exactly 0.5

 

[robertjordan]

Don’t round up. Round off. It should work unless you get exactly 0.5

I'm not sure what round off means.

If round off means raise anything with a decimal >= .5 the next whole number and anything with a decimal <.5 to the next whole number down, then the example will still lead to 18 pieces being assigned.

 

[Dale]

I think that is just because of being exactly 0.5.

 

[robertjordan]

I think that is just because of being exactly 0.5.

Another example is:

w₁ = 11
w₂ = 39
w₃ = 3
W = 53
P = 25

ROUND(P*w₁/W) = 5
ROUND(P*w₂/W) = 18
ROUND(P*w₃/W) = 1

This sums to 24 but we have 25 pieces.

 

[kuruman]

This sums to 24 but we have 25 pieces.

I faced the same issue when I rounded so I solved the problem by assigning to the last person whatever number of pieces are left unassigned. Simple, no?

 

[Dale]

Yup, you are right. No 0.5’s so that isn’t the problem