Showing filling a container with rectangles is hard by reducing from SUBSET-SUM
-
16-10-2019 - |
Pergunta
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!
Solução
Hint: Follow frafl's advice and set $b_i = h = 1$.
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange