<p>The packages are constructed in that way to turn the problem into a one-dimensional problem (Partition is one-dimensional). If all the packages have width 5 and height 3 (i.e. exactly the width and height of the truck), then the only dimension that matters is the length (the first coordinate) in order to make them fit because they fit exactly in the other two dimensions. The factor $\frac{4}{A}$ is just to make the sum of all the values exactly $4$ (twice the truck's length). That way the packages fit in the two trucks if and only if there is a partition of them into two sets of packages such that the total length of each set is exactly 2, which as argued in the solution is equivalent to have a partition for the original set of values $a_i$.</p>

<p>Notice that the largest dimensions are the ones fixed because that way there is only one feasible orientation for the packages (they cannot be rotated because they would not fit).</p>

<p>Hope it is clear. Best regards!</p>

CC BY-SA 3.0
2016-07-27T09:53:56.563Z
The normal problem with the packages is three-dimensional because we have $3$ unknown variables, $x_i, y_i, z_i$ and the partition problem is one-dimensional because we have just the value $a_i$ ?
Mary Star
CC BY-SA 3.0
2016-07-27T10:25:27.647Z
Your last claim is wrong because you cannot easily show that rotating the packages cannot give a better fit. That is why we should use the largest dimensions of the truck, because it is easy to prove that the package must be placed in that one orientation only.
user21820
CC BY-SA 3.0
2016-07-27T10:34:09.897Z
@MaryStar: Those are not unknown; they are given. The unknown variables are the positions and rotations, $6$ for each package!
user21820
CC BY-SA 3.0
2016-07-27T11:02:43.023Z
@user21820 You are right, thanks. I edited the answer.
W. Gálvez
CC BY-SA 3.0
2016-07-28T00:34:44.833Z
I haven't really understood why the largest dimensions have to be fixed. Could you explain it to me?
Mary Star
CC BY-SA 3.0
2016-07-28T00:37:54.940Z
So, does it mean that the problem with the packages is $6$-dimensional? @user21820
Mary Star
CC BY-SA 3.0
2016-07-28T02:21:43.910Z
@MaryStar: I said 6 for each package. I think you don't understand reductions. A reduces to B iff every instance of A can be solved by using an oracle that solves B. Expand the definition. What does it mean by "solved"?
user21820
CC BY-SA 3.0
2016-07-27T09:13:30.387Z
2016-07-27T11:01:56.353Z
2016-07-27T11:01:56.353Z
W. Gálvez
<p>I am looking at the following solved exercise: </p>

<p><a href="https://i.sstatic.net/YDfZv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/YDfZv.png" alt="enter image description here"></a></p>

<p>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?</p>

CC BY-SA 3.0
2016-07-28T02:57:00.820Z
You are on the wrong site. Please read our [help/on-topic]. See also [cs.se] which has a broader scope.
Kaveh
<computability><reductions><np-complete>
Could you explain to me the reduction?
Mary Star
# Could you explain to me the reduction?

(Asked by: username_0 on 2016-07-27)

I am looking at the following solved exercise:

[![enter image description here](https://i.sstatic.net/YDfZv.png)](https://i.sstatic.net/YDfZv.png)

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?

**Tags:** computability, reductions, np-complete
> **Comments:**
> **username_1**: You are on the wrong site. Please read our [help/on-topic]. See also [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_2 on 2016-07-27. Score: 1

The packages are constructed in that way to turn the problem into a one-dimensional problem (Partition is one-dimensional). If all the packages have width 5 and height 3 (i.e. exactly the width and height of the truck), then the only dimension that matters is the length (the first coordinate) in order to make them fit because they fit exactly in the other two dimensions. The factor $\frac{4}{A}$ is just to make the sum of all the values exactly $4$ (twice the truck's length). That way the packages fit in the two trucks if and only if there is a partition of them into two sets of packages such that the total length of each set is exactly 2, which as argued in the solution is equivalent to have a partition for the original set of values $a\_i$.

Notice that the largest dimensions are the ones fixed because that way there is only one feasible orientation for the packages (they cannot be rotated because they would not fit).

Hope it is clear. Best regards!

> **Comments:**
> **username_0**: The normal problem with the packages is three-dimensional because we have $3$ unknown variables, $x_i, y_i, z_i$ and the partition problem is one-dimensional because we have just the value $a_i$ ?  
> **username_3**: Your last claim is wrong because you cannot easily show that rotating the packages cannot give a better fit. That is why we should use the largest dimensions of the truck, because it is easy to prove that the package must be placed in that one orientation only.  
> **username_3**: @MaryStar: Those are not unknown; they are given. The unknown variables are the positions and rotations, $6$ for each package!  
> **username_2**: @user21820 You are right, thanks. I edited the answer.  
> **username_0**: I haven't really understood why the largest dimensions have to be fixed. Could you explain it to me?  
> **username_0**: So, does it mean that the problem with the packages is $6$-dimensional? @user21820  
> **username_3**: @MaryStar: I said 6 for each package. I think you don't understand reductions. A reduces to B iff every instance of A can be solved by using an oracle that solves B. Expand the definition. What does it mean by "solved"?  

---

