Fiquei pensando em isso depois de hugo comentar. Acho que a solucao é um pouco diferente, pois devemos preencher uma tabela que tem como índice menor
min{0,soma de todos os números negativos}
e índice maior
max{soma procurada,soma de todos os números positivos}
Depois se roda o algoritmo conhecido com umas pequenas modificoes e o problema é resolvido.
O que fica feio ao fazer isto é que a complexidade nao é mais O(M*n), onde M é a soma procurada e n é o número de elementos, agora a complexidade é O(H*n), onde H é a diferenca entre a soma máxima e a soma mínima que pode-se fazer com os elementos.
No caso geral, onde para qualquer M sempre existe solucao, a complexidade nao depende mais de M, senao só dos elementos do conjunto, o que deixa de ser input-sensitive. Pelo menos sempre é bom nao deixar nada no ar, como essa questao.
Interessante. Acho que você tem razão.
Como, exatamente, seria preenchida a tabela
da programação dinâmica?
"No caso geral, onde para qualquer M sempre
existe solucao, a complexidade nao depende
mais de M, senao só dos elementos do conjunto,
o que deixa de ser input-sensitive."
Não entendi esta parte.
Como, exatamente, seria preenchida a tabela
da programação dinâmica?
"No caso geral, onde para qualquer M sempre
existe solucao, a complexidade nao depende
mais de M, senao só dos elementos do conjunto,
o que deixa de ser input-sensitive."
Não entendi esta parte.
Bom, a tabela seria preenchida de um jeito bem parecido ao do algoritmo original, só que devemos ter cuidado com os números negativos, para isso podemos fazer um truque que é somar a cada valor encontrado uma constante grande de manera que o resultado seja >=0.
Bom, sobre o que você nao entendeu: sabemos que a complexidade do algoritmo é O(n*M), onde n é o número de elementos e M é a soma procurada, nao precisamos preencher uma tabela que encontre valores maiores do que M. Agora, com o caso dos números negativos, é possivel chegar a esse número M com a soma de dos grupos de números A e B, tal que A é positivo e B é negativo, daí temos que A > M, entao precisamos preencher uma tabela que encontre valores maiores do que M, algo nao necesario no algoritmo original. O que é interessante do algoritmo original é que a complexidade sempre depende de M e do número de elementos, mas no caso com números negativos, a complexidade nao depende de M, só de n e dos valores desses n elementos, por isso falei que já nao era mais input-sensitive, o que nao é tao certo, pois a complexidade depende dos n elementos, mas já nao depende de M.
Bom, sobre o que você nao entendeu: sabemos que a complexidade do algoritmo é O(n*M), onde n é o número de elementos e M é a soma procurada, nao precisamos preencher uma tabela que encontre valores maiores do que M. Agora, com o caso dos números negativos, é possivel chegar a esse número M com a soma de dos grupos de números A e B, tal que A é positivo e B é negativo, daí temos que A > M, entao precisamos preencher uma tabela que encontre valores maiores do que M, algo nao necesario no algoritmo original. O que é interessante do algoritmo original é que a complexidade sempre depende de M e do número de elementos, mas no caso com números negativos, a complexidade nao depende de M, só de n e dos valores desses n elementos, por isso falei que já nao era mais input-sensitive, o que nao é tao certo, pois a complexidade depende dos n elementos, mas já nao depende de M.
Não vejo como somar uma constante grande
pode ajudar.
Quanto ao resto acho que pode funcionar.
O melhor a fazer agora é escrever o pseudocódigo!
pode ajudar.
Quanto ao resto acho que pode funcionar.
O melhor a fazer agora é escrever o pseudocódigo!