Uma variação no problema da mochila: como resolver o problema da Partição Equal Subset Sum em Java

Atualização: leia sobre como otimizar a complexidade do espaço da solução de programação dinâmica no meu artigo de acompanhamento aqui.

Anteriormente, escrevi sobre como resolver o Problema da Mochila (KP) com programação dinâmica. Você pode ler sobre isso aqui.

Hoje eu quero discutir uma variação do KP: o problema de soma de subconjuntos da partição. Vi esse problema pela primeira vez no Leetcode - foi isso que me levou a aprender e escrever sobre o KP.

Esta é a declaração do problema (reproduzida parcialmente sem exemplos):

Dada uma matriz não vazia contendo apenas números inteiros positivos, encontre se a matriz pode ser particionada em dois subconjuntos, de modo que a soma dos elementos nos dois subconjuntos seja igual.

Para a declaração completa do problema, com restrições e exemplos, consulte o problema do Leetcode.

Programaçao dinamica

Como no KP, resolveremos isso usando programação dinâmica. Como essa é uma variação do KP, a lógica e a metodologia são amplamente semelhantes.

Solução

Alojaremos nossa solução em um método que retorne um valor booleano - true se a matriz puder ser particionada em subconjuntos iguais e, caso contrário, false.

Etapa 1: Proteção contra soma de matriz ímpar

Trivialmente, se todos os números na matriz somam uma soma ímpar, podemos retornar false. Só prosseguimos se a matriz somar uma soma uniforme.

Etapa 2: Criando a Tabela

Em seguida, criamos a tabela.

As linhas da tabela representam o conjunto de elementos da matriz a serem considerados, enquanto as colunas da tabela indicam a soma que queremos chegar. Os valores da tabela são simplesmente valores booleanos, indicando se é possível chegar a uma soma (coluna) com um conjunto de elementos da matriz (linha).

Concretamente, a linha i representa um conjunto de elementos da matriz dos índices 0 a (i-1). O motivo desse deslocamento de 1 é porque a linha 0 representa um conjunto vazio de elementos. Portanto, a linha 1 representa o primeiro elemento da matriz (índice 0), a linha 2 representa os dois primeiros elementos da matriz (índices 0–1) e assim por diante. No total, criamos n + 1 linhas, incluindo 0.

Queremos apenas saber se podemos somar exatamente a metade da soma total da matriz. Portanto, precisamos criar apenas colunas totalSum / 2 + 1, inclusive 0.

Etapa 3: preencher previamente a tabela

Podemos começar imediatamente a preencher as entradas para os casos base em nossa tabela - linha 0 e coluna 0.

Na primeira linha, todas as entradas - exceto a primeira - devem ser falsas. Lembre-se de que a primeira linha representa um conjunto vazio. Naturalmente, não conseguimos chegar a nenhuma soma alvo - número da coluna - exceto 0.

Na primeira coluna, toda entrada deve ser verdadeira. Sempre podemos, trivialmente, chegar a uma soma alvo de 0, independentemente do conjunto de elementos com os quais temos que trabalhar.

Etapa 4: Criando a tabela (o ponto crucial do problema)

Alguma entrada na tabela na linha ie coluna j é verdadeira (atingível) se uma das três condições a seguir for atendida:

  1. a entrada na linha i-1 e na coluna j é verdadeira. Lembre-se do que o número da linha representa. Portanto, se somos capazes de atingir uma soma específica com um subconjunto dos elementos que temos atualmente, também podemos atingir essa soma com nosso conjunto atual de elementos - simplesmente não usando os elementos extras. Isso é trivial. Vamos chamar isso de prevRowIsTrue.
  2. O elemento atual é exatamente a soma que queremos obter. Isso também é trivialmente verdade. Vamos chamar isso deExactMatch.
  3. Se as duas condições acima não forem satisfeitas, ainda temos uma maneira de atingir nossa soma alvo. Aqui, usamos o elemento atual - o elemento adicional no conjunto de elementos em nossa linha atual em comparação com o conjunto de elementos na linha anterior - e verificamos se conseguimos atingir o restante da soma de destino. Vamos chamar isso de canArriveAtSum.

Vamos desempacotar a condição 3. Só podemos usar o elemento atual se ele for menor que a soma da nossa meta. Se forem iguais, a condição 2 seria atendida. Se for maior, não podemos usá-lo. Portanto, o primeiro passo é garantir que o elemento atual

Depois de usar nosso elemento atual, ficamos com o restante de nossa soma alvo. Em seguida, verificamos se isso é possível verificando a entrada correspondente na linha acima.

Como no KP normal, queremos construir progressivamente nossa tabela de baixo para cima. Começamos com os casos básicos, até chegarmos à nossa solução final.

Etapa 5: retornando a resposta

Simplesmente retornamos retorno mat [nums.length] [totalSum / 2].

Código de trabalho

Obrigado pela leitura!