# Showing filling a container with rectangles is hard by reducing from SUBSET-SUM

Given a set of rectangles, $D = \{ (a_1, b_1), (a_2, b_2) \dots , (a_n, b_n) \}$, where in each pair $(a_i, b_i)$, $a_i$ represents the height of the rectangle and $b_i$ the width, and given another pair $(w, h)$ representing the width and height of a container $C$, does exist a way that taking some of the squares in $D$, the whole container C is perfectly filled? Here, $a_i, b_i, w, h \in \mathbb N$.

I am trying to reduce it from Subset Sum, but can't find the way... Hope you guys can give me a hint over it!

• What did you try? What about setting the height to $1$? – frafl May 21 '13 at 21:59
• I've tried the following: I've constrained $a_i = b_i$ and $w=h$. so I can have a kind of instance from SS to A, like this: $\sum_{i\in \{1..n\}}a_i^2\cdot X_i = c^2$, $a_i\cdot X_i \le c$ but still getting things overlaped or out of bounds. When saying "yes" to SS it may occur that I say "no" for A, for example: $c=5,$ and I take certain $i,j$ so that $a_i = 4, a_j = 5$, it's a "yes" for SS and "no" for A. I haven't try to set $c=1$ but I dont know if it will work, because $a_i, c\in \mathbb N$. (I should add this into a EDIT up there) – Mus May 21 '13 at 22:34

Hint: Follow frafl's advice and set $b_i = h = 1$.

• Sorry, but I can't figure it out with $b_i = a_i = h = w = 1$... so the eq for my instance would be $X_1 + ... + X_n = 1$ and I am trying to pick which $X_i$ is set to one and which others to zero? Wouldn't that be incorrect as I am excessively constraining the main problem A? – Mus May 21 '13 at 22:58
• I never said that $a_i = w = 1$. – Yuval Filmus May 21 '13 at 23:03