Problema relacionado ao particionamento definido

Question

Deixe $ a_j= {(a ^ i_j, b ^ i_j) ~: ~ 0 \ leq i \ leq n, \ text {e} a ^ i_j, b ^i_j \ in \ mathbb {z} ^ +} $

Dados conjuntos $ a_1, \ ldots, A_ {p} $ e um inteiro positivo $ k $ , o problema é verificar se existe um elemento $ (A ^ {I_J} _J, B ^ {I_J} _J) $ de cada $ a_j $ tais que $ \ sum_ {j} ^ {} a ^ {i_j} _J \ GEQ K $ e Class="contêiner math-contenter"> $ \ sum_ {j} ^ {} b ^ {i_j} _J \ GEQ K $ .

Parece que o problema está relacionado ao problema de particionamento, no entanto, não tenho certeza de como obter uma redução do problema de particionamento definido.Alguém pode me ajudar a encontrar o algoritmo para resolver esse problema?

Answer 1

Deixe $ opt [t, x] $ ser o valor máximo de $ \ sum_ {j= 1} ^ t b_j ^ {i_j} $ que pode ser atingido selecionando um elemento $ (A_J ^ {I_J}, A_J ^ {I_J}) $ de cada da primeira $ t $ Define com a restrição que $ \ sum_ {j= 1} ^ i A_J ^ {I_J} \ GE X $ . Se a restrição não puder ser satisfeita, deixe $ opt [t, x]= - \ FATTY $ .

De acordo com a definição acima, temos $ opt [0, 0]= 0 $ e $ opt [0, x]= - \ Fgrty $ para $ x> 0 $ .

para $ t> 0 $ temos: $$ Opt [t, x]=max_ {i= 1, \ dots, n} \ left (b_t ^ i + opt [t-1, \ max \ {x-a_t ^ i, 0 \}] \ direita). $$

A resposta ao seu problema é "sim" se e somente se $ opt [p, k] \ ge $ .

Como há $ o (p \ CDOT K) $ subproblemas, cada um dos quais pode ser resolvido em $ O (n) $ tempo, a complexidade geral deste algoritmo é $ o (p \ cdot k \ cdot n) $ .

Para mostrar que o seu problema é NP-Hard, você pode perceber que é uma generalização do problema da partição: Dado um conjunto $ s={x_1, \ Dots, x_m \ } $ de $ m $ inteiros não negativos, decida se há um subconjunto $ S '$ < / span> de $ s $ tal que $ \ sum_ {x \ in s '} x=frac {1} {2} \ sum_ {x \ in s} x $ .

Para ver isso, definir $ n= 2 $ , $ p= M $ , $ a_j= {(x_j, 0), (0, x_j) \} $ , e $ k=frac {1 } {2} \ sum_ {x \ in s} x $ .