2
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\begingroup$ What did you try? What about setting the height to $1$? $\endgroup$
    – frafl
    Commented May 21, 2013 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
    Commented May 21, 2013 at 22:34

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented May 21, 2013 at 22:58
  • $\begingroup$ I never said that $a_i = w = 1$. $\endgroup$
    – Yuval Filmus
    Commented May 21, 2013 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.