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!

  • $\begingroup$ What did you try? What about setting the height to $1$? $\endgroup$ – frafl May 21 '13 at 21:59
  • $\begingroup$ 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) $\endgroup$ – Mus May 21 '13 at 22:34

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

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Mus May 21 '13 at 22:58
  • $\begingroup$ I never said that $a_i = w = 1$. $\endgroup$ – Yuval Filmus May 21 '13 at 23:03

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.