Compartilhamento de tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

um,Matriz bidimensional

1、equação de transição de estado：

• Não coloque itensi : Deduzido de dp[i - 1][j], ou seja, a capacidade da mochila é j e o valor máximo do item i não está colocado nela neste momento, dp[i][j] é dp[i -. 1][j]. (Na verdade, quando o peso do item i é maior que o peso da mochila j, o item i não pode ser colocado na mochila, então o valor na mochila ainda é o mesmo de antes.)
• Coloque o item eu: Deduzido de dp[i - 1][j - peso[i]], dp[i - 1][j - peso[i]] é a capacidade máxima da mochila sem o item i quando a capacidade é j - peso[ i] valor, então dp[i - 1][j - peso[i]] + valor[i] (o valor do item i) é o valor máximo obtido colocando o item i na mochila

Portanto, a fórmula recursiva: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - peso[i]] + valor[i]);

2. Inicialização

(1) A partir da definição de dp[i][j], se a capacidade da mochila j for 0, ou seja, dp[i][0], independente dos itens selecionados, o valor total da mochila deverá ser 0.

(2) Equação de transição de estado dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - peso[i]] + valor[i]); visto que i é derivado de i-1, portanto deve ser inicializado quando i for 0.

dp[0][j], ou seja: i é 0, ao armazenar o item número 0, valor máximo que uma mochila de cada capacidade pode armazenar.

Então é óbvio que quando j < peso[0], dp[0][j] deve ser 0, pois a capacidade da mochila é menor que o peso do item numerado 0.

Quando j >= peso[0], dp[0][j] deve ser valor[0], pois a capacidade da mochila é suficiente para conter o item número 0.

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

(3) Outra inicialização de subscrito:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - peso[i]] + valor[i])

dp[1][1] = max(dp[0][1], dp[0][1- peso[i]] + valor[i]) deve estar à esquerda e acima dele,

Portanto, ele deve ter sido inicializado e pode ser definido com qualquer valor. Por conveniência, ele é inicializado com 0 por padrão.

2. Unidimensional (matriz rolante)

1. No array dp unidimensional, dp[j] significa: uma mochila com capacidade j pode transportar itens com valor máximo de dp[j]

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

2. Inicialização

(1) dp[0]=0, pois o valor máximo de itens transportados por uma mochila com capacidade 0 é 0.

(2) Suponha que o valor dos itens seja maior que 0,Para não ser substituído pelo valor inicial, então dpInicialização da matrizQuando , eles são todos inicialmente 0

3. Ordem transversal

Percorrer na ordem inversa

Explicação 1: O valor no final da lista precisa ser determinado comparando-o com o valor anterior obtido ao percorrer o nível anterior.

Explicação 2: Existe apenas uma mochila 01 para cada mochila. O fato de esta bolsa ser colocada ou não está relacionado ao status da bolsa anterior. A matriz à esquerda é uma quantidade que descreve o status da bolsa anterior e o número na. o direito é um status pendente da bolsa atual. No código, o número à esquerda é necessário para determinar a matriz à direita, portanto, o número à esquerda não pode ser destruído antes que o número à direita seja calculado.

Explicação 3: Para duas dimensões, o resultado de cada novo número dp que tenho vem de cima e da esquerda, na verdade, deveria ser assim em uma dimensão, mas em uma dimensão, se ainda for da esquerda para a direita, então; minha esquerda real Os números foram atualizados ( O lado esquerdo não é mais o lado esquerdo “original”!Isso causará alguma contagem dupla ), mesmo que o topo ainda seja o topo original, o número obtido está incorreto.E se percorrermos da direita para a esquerda na camada mochila (camada interna), então o elemento à esquerda sempre seráNão será substituído por novos valores devido à minha operação anterior., para que o valor correto possa ser obtido.

3. Aplicação

1. Dado um array não vazio contendo apenas inteiros positivos. É possível dividir esta matriz em dois subconjuntos de modo que a soma dos elementos dos dois subconjuntos seja igual?

Nota: Os elementos em cada array não excederão 100 e o tamanho do array não excederá 200

Exemplo 1:

• Entrada: [1, 5, 11, 5]
• Saída: verdadeiro
• Explicação: A matriz pode ser dividida em [1, 5, 5] e [11]

analisar:

O item sou eu,

O peso é nums[i], o valor também é nums[i] e o volume da mochila é sum/2.

Semelhante a 01 mochila

Equação de transição de estado:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;

2. Há uma pilha de pedras e o peso de cada pedra é um número inteiro positivo.

A cada rodada, escolha duas pedras quaisquer e esmague-as. Suponha que os pesos das pedras sejam x e y, respectivamente, e x <= y. Então os possíveis resultados da britagem são os seguintes:

Se x == y, então ambas as rochas serão completamente esmagadas;

Se x! = y, então a pedra de peso x se quebrará completamente e a pedra de peso y terá um novo peso de yx.

No final, no máximo sobrará apenas uma pedra. Retorna o menor peso possível desta pedra. Se não houver mais pedras, retorne 0.

Exemplo:

• Entrada: [2,7,4,1,8,1]
• Saída: 1

analisar:

Tente dividir as pedras em duas pilhas de mesmo peso, de modo que a menor pedra restante após a colisão

Em seguida, divida-o em duas pilhas de pedras. O peso total de uma pilha de pedras é dp[alvo], e o peso total da outra pilha é a soma - dp[alvo].

Ao calcular a meta, meta = soma / 2 porque é arredondado para baixo, então soma - dp[target] deve ser maior ou igual a dp[target]

Então o peso mínimo da pedra restante após a colisão é (soma - dp[target]) - dp[target]

for (int i = 0; i < stones.length; i++) {
//采用倒序
    for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}
//结果
sum - 2 * dp[target];

citado de:Código de notas aleatórias