A idéia básica do algoritmo ganancioso
1. Estabeleça um modelo matemático para descrever o problema.
2. Divida os problemas resolvidos em vários subproblemas.
3. Resolva cada subproblema e obtenha a solução ideal local para o subproblema.
4. Sincronize a solução ideal local do subproblema em uma solução para a solução original do problema.
O processo de implementação deste algoritmo:
Começando de uma certa solução inicial para o problema;
Enquanto pode avançar para um determinado objetivo geral
Encontre um elemento de solução da solução viável;
Uma solução viável para o problema é composta por todos os elementos da solução.
Natureza seletiva gananciosa
A chamada natureza de seleção gananciosa significa que a solução ideal geral do problema que você está procurando pode ser alcançada através de uma série de escolhas ideais locais. Problema atual sem considerar. Este é o primeiro elemento básico da viabilidade de algoritmos gananciosos.
Algoritmos gananciosos fazem escolhas itineransamente gananciosas, e cada vez que uma escolha gananciosa é feita, o problema que você está procurando é reduzido a um subproblema menor.
Para um problema específico, para determinar se tem uma natureza de escolha gananciosa, é necessário provar que a escolha gananciosa feita em cada etapa leva à solução ideal geral para o problema.
2. Propriedades ideais da subestrutura <Br /> Quando a solução ideal de um problema contém a solução ideal de seu subproblema, diz-se que esse problema possui as propriedades subestruturais ideais. A natureza ideal da subestrutura do problema é um recurso essencial que pode ser resolvido por algoritmos gananciosos.
O processo geral de ganância
A cópia do código é a seguinte:
Ganancioso (c) // c é o conjunto de entrada do problema, ou seja, o conjunto de candidatos
{
S = {};
enquanto (não soluções (s)) // set s não constitui uma solução para o problema
{
x = selecione (c);
Se viável (s, x) // julgar se a solução após adicionar x ao conjunto S é viável
S = s+{x};
C = c- {x};
}
retorno s;
Descrição do problema:
Atualmente, existem moedas com valores de face de 2 Jiao 5 centavos, 1 jiao 5 centavos, 5 centavos e 1 centavo.
Análise de problemas:
De acordo com o bom senso, quando vamos à loja para comprar coisas e encontrar dinheiro, o chefe sempre nos dá a denominação máxima primeiro. Se o chefe pedir pontuações ou alguns centavos, você definitivamente não fará isso. De fato, este é um problema típico de escolha gananciosa.
Projeto de algoritmo e implementação do problema :
Deixe -me dar um exemplo primeiro. Ele procura isso assim? Faça isso, então o chefe só pode me dar, eu tenho 3 25 pontos e recebi 24 a menos, então tive que me dar 2 10 pontos e 4 1 pontos.
A cópia do código é a seguinte:
// aritmético para encontrar mudanças
// Entrada: Matriz M, armazene o número de valores de face organizados de grande a pequena sequência.
// Saída: Array num, compare o número de moedas com diferentes valores de denominação na matriz m e encontre um plano de dinheiro
public static int [] zhaoqian (int m [], int n)
{
int k = m.Lengen;
int [] num = new int [k];
para (int i = 0; i <k; i ++)
{
num <i> = n/m <i>;
n = n%m <i>;
}
retornar num;
}
A cópia do código é a seguinte:
Classe pública Zhaoqian
{
public static void main (string [] args)
{
int m [] = {25,10,5,1};
int n = 99;
int [] num = new int [M.Length];
num = zhaoqian (m, n);
System.out.println (n+"plano de identificação de dinheiro:");
para (int i = 0; i <M.Length; i ++)
System.out.println (num <i>+"zip"+m <i>+"valor nominal");
}
public static int [] zhaoqian (int m [], int n)
{
int k = m.Lengen;
int [] num = new int [k];
para (int i = 0; i <k; i ++)
{
num <i> = n/m <i>;
n = n%m <i>;
}
retornar num;
}
}
O exposto acima é todo o conteúdo deste artigo, espero que você possa gostar.