Reduction of the partition problem

[mathmari]

Hey!

A trucking company has two same trucks. The luggage space is a cuboid with floor area $2m\times 5m$ and height $3m$. The packages that the comany has to deliver are also cuboid.
The packages must be distributed into the two trucks.
The problem is defined as followed:

• $n$ packages are given with measurements $(x_1, y_1, z_1), \dots , (x_n, y_n, z_n)$.
• It is asked if the packages fit in the two trucks.

Show that this problem is NP-complete.

To show that, the reduction of the partition problem is needed, as follows.
Let $(a_1, \dots , a_n)$ be the input for PARTITION. Let $A=\sum_{i=1}^n a_i$. We construct for each number $a_i$ a package of measurement $(\frac{4}{A}a_i, 5,3)$ for the above problem. Then for a set $I\subseteq [n]$ we have that $$\sum_{i\in I}a_i=\frac{A}{2}\Leftrightarrow \sum_{i\in I}\frac{4}{A}a_i=\frac{4}{A}\cdot \frac{A}{2}=2$$
Therefore, there is the partition of $(a_1, a_2, \dots , a_n)$ into two same sets iff the packages fit in the two trucks. I haven't really understood at the reduction the part that we construct for each number $a_i$ a package of measurement $(\frac{4}{A}a_i, 5,3)$. Why do we consider this measurement? (Wondering)

 

[Future Bruno]

We consider this measurement because it allows us to relate the sum of the packages' measurements with the sum of the numbers in the partition problem. Specifically, we want to show that there is a partition of the numbers in the partition problem into two sets of equal sum if and only if the packages fit into the two trucks. To do this, we need to make sure that the sum of the packages' measurements is equal to the sum of the numbers in the partition problem. So, we choose a measurement for the packages that corresponds to the sum of the numbers in the partition problem. In this case, the total floor area of the two trucks is $2\times 5=10m^2$, so we set each package's floor area to $\frac{4}{A}a_i$ to ensure that the total surface area of the packages is equal to 10 (since $\sum_{i=1}^n \frac{4}{A}a_i=10$).