Problema de programação complicado que estou tendo problemas para entender
https://stackoverflow.com/questions/2320138
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Primeiro, deixe-me dizer que isso não é lição de casa (eu sou um aluno de nível A, isso não é nada próximo do que resolvemos resolver (isso é caminho mais difícil)), mas mais um problema que estou tentando melhorar para melhorar minha lógica de programação.
Pensei em um cenário em que há uma variedade de números inteiros aleatórios, por exemplo, digamos 10 números inteiros. O usuário inserirá um número para o qual deseja contar, e o algoritmo tentará descobrir quais números são necessários para fazer essa soma. Por exemplo, se eu quisesse fazer a soma 44 dessa variedade de números inteiros:
myIntegers = array(1, 5, 9, 3, 7, 12, 36, 22, 19, 63);
A saída seria:
36 + 3 + 5 = 44
Ou algo nesse sentido. Espero me deixar claro. Como um bônus adicional, gostaria de fazer com que o algoritmo escolha o mínimo de números possível para fazer a soma necessária ou dar um erro se a soma não puder ser feita com os números fornecidos.
Pensei em usar recursão e iteração através da matriz, adicionando números repetidamente até que a soma seja atendida ou passada. Mas o que eu não consigo entender é o que fazer se o algoritmo passar pela soma e precisar ser seletivo sobre quais números escolher da matriz.
Não estou procurando um código completo ou um algoritmo completo, só quero suas opiniões sobre como devo prosseguir com isso e talvez compartilhar algumas dicas ou algo assim. Provavelmente começarei a trabalhar nisso esta noite. : P
Como eu disse, não o dever de casa. Só eu querendo fazer algo um pouco mais avançado.
Obrigado por qualquer ajuda que você possa oferecer. :)
Solução
Você está olhando para o Problema da mochila
O problema do Knapsack ou o problema da mochila é um problema na otimização combinatória: dado um conjunto de itens, cada um com peso e valor, determine o número de cada item a ser incluído em uma coleção para que o peso total seja menor que um determinado limite e O valor total é o mais grande possível. Ele deriva seu nome do problema enfrentado por alguém que é restrito por uma mochila de tamanho fixo e deve preenchê-lo com os itens mais úteis.
Editar: Seu caso especial é o Problema da soma do subconjunto
Outras dicas
Vai Soma do subconjunto Faz? ;
Este é o clássico Mochila Problema que você veria no curso de algoritmos de nível universitário (ou pelo menos eu o vi então). O melhor para resolver isso no papel e a solução no código deve ser relativamente fácil de se exercitar.
Editar: Uma coisa a considerar é programaçao dinamica.
Seu problema está relacionado ao Problema da soma do subconjunto. Você precisa tentar todas as combinações possíveis no pior caso.
Receio que não há atalhos aqui. Além do que as outras pessoas disseram, sobre o problema específico que esse é etc., aqui estão alguns conselhos práticos para oferecer um ponto de partida:
Eu classificava a matriz e recebia a soma de entrada m, encontraria o primeiro número na matriz menor que m, chame-o n (Este é o seu primeiro número possível para a soma) e comece a partir do maior complemento possível (m-n), trabalhando no seu caminho.
Se você não encontrar uma correspondência precisa, escolha o mais alto disponível, ligue para o, (esse agora é o seu segundo número) e procure o terceiro a partir de (m-n-o) e desça novamente.
Se você não encontrar uma correspondência precisa, comece com o próximo número n (índice de n original no índice-1) e faça o mesmo. Você pode continuar fazendo isso até encontrar uma correspondência precisa para dois números. Se nenhuma correspondência para a soma for encontrada para dois números, inicie o processo novamente, mas expanda -o para incluir um terceiro número. E assim por diante.
Isso pode ser feito recursivamente. Pelo menos essa abordagem garante que, quando você encontrar uma correspondência, será o que é o menor número possível no conjunto, formando a soma total de entrada.
Potencialmente, no pior caso, você acaba passando por todo o lote.
Editar: Como Venr aponta corretamente, minha primeira abordagem estava incorreta. Abordagem editada para refletir isso.
Há um algoritmo randomizado muito eficiente para esse problema. Eu sei que você já aceitou uma resposta, mas estou feliz em compartilhar de qualquer maneira, só espero que as pessoas ainda verifiquem essa pergunta :).
Let Used = list of numbers that you sum.
Let Unused = list of numbers that you DON'T sum.
Let tmpsum = 0.
Let S = desired sum you want to reach.
for ( each number x you read )
toss a coin:
if it's heads and tmpsum < S
add x to Used
else
add x to Unused
while ( tmpsum != S )
if tmpsum < S
MOVE one random number from Unused to Used
else
MOVE one random number from Used to Unused
print the Used list, containing the numbers you need to add to get S
Isso será muito mais rápido que a solução de programação dinâmica, especialmente para entradas aleatórias. Os únicos problemas são que você não pode detectar com segurança quando não há solução (você pode deixar o algoritmo funcionar por alguns segundos e, se não terminar, assuma que não há solução) e que você não pode ter certeza de que obterá a solução com número mínimo de elementos escolhidos. Novamente, você pode adicionar alguma lógica para fazer com que o algoritmo continue e tentando encontrar uma solução com menos elementos até que certas condições de parada sejam atendidas, mas isso o tornará mais lento. No entanto, se você estiver interessado apenas em uma solução que funcione e você tenha muitos números e a soma desejada pode ser muito grande, isso provavelmente é melhor que o algoritmo DP.
Outra vantagem dessa abordagem é que ela também funcionará para números negativos e racionais, sem modificações, o que não é verdadeiro para a solução DP, porque a solução DP envolve o uso de somas parciais como índices de matriz, e os índices podem ser apenas números naturais. É claro que você pode usar hashtables, por exemplo, mas isso tornará a solução DP ainda mais lenta.
Não sei exatamente como é chamado essa tarefa, mas parece que é meio que http://en.wikipedia.org/wiki/knapsack_problem.
Heh, vou tocar a carta "especificação incompleta" (ninguém disse que os números não poderiam parecer mais de uma vez!) E reduzi -lo ao problema de "fazer mudanças". Classifique seus números em ordem decrescente, encontre o primeiro a menos que a soma desejada e subtraia a sua soma (divisão e restos podem acelerar isso). Repita até a soma = 0 ou nenhum número menor que a soma é encontrada.
Para completude, você precisaria acompanhar o número de adição de cada soma e, é claro, gerar as seqüências adicionais, acompanhando o primeiro número que você usa, pulando isso e repetindo o processo com os números adicionais. Isso resolveria o problema (7 + 2 + 1) sobre (6 + 4).
Repetindo a resposta de outras pessoas: é um problema de soma do subconjunto. Pode ser resolvido com eficiência pela técnica de programação dinâmica.
O seguinte ainda não foi mencionado: o problema é pseudo-p (ou NP-completo em sentido fraco).
A existência de um algoritmo (com base na programação dinâmica) polinômio em s (onde s é a soma) e n (o número de elementos) prova essa reivindicação.
Cumprimentos.
OK, escrevi um programa C ++ para resolver o problema acima. O algoritmo é simples :-)
Antes de tudo, organize qualquer matriz que você tenha em ordem decrescente (eu codifiquei a matriz em forma descendente, mas você pode aplicar qualquer um dos algoritmos de classificação).
Em seguida, peguei três pilhas n, pos e soma. O primeiro armazena o número para o qual uma possível combinação de soma pode ser encontrada, o segundo mantém o índice da matriz de onde iniciar a pesquisa, o terceiro armazena os elementos cuja adição fornecerá o número que você insere.
A função procura o maior número da matriz que é menor ou igual ao número inserido. Se for igual, simplesmente empurra o número para a pilha de soma. Caso contrário, ele empurra o elemento de matriz encontrado para a pilha de soma (temporariamente) e encontra a diferença entre o número a procurar e o número encontrado e, em seguida, ele executa a recursão.
Deixe-me mostrar um exemplo:- encontrar 44 em {63,36,22,19,12,9,7,5,3,1}}
Os primeiros 36 serão pressionados em soma (maior número menor que 44) 44-36 = 8 serão pressionados em n (o próximo número a procurar) 7 será pressionado no SUM 8-7 = 1 será pressionado em n 1 será empurrado em soma
Assim 44 = 36+7+1 :-)
#include <iostream>
#include<conio.h>
using namespace std;
int found=0;
void func(int n[],int pos[],int sum[],int arr[],int &topN,int &topP,int &topS)
{
int i=pos[topP],temp;
while(i<=9)
{
if(arr[i]<=n[topN])
{
pos[topP]=i;
topS++;
sum[topS]=arr[i];
temp=n[topN]-arr[i];
if(temp==0)
{
found=1;
break;
}
topN++;
n[topN]=temp;
temp=pos[topP]+1;
topP++;
pos[topP]=temp;
break;
}
i++;
}
if(i==10)
{
topP=topP-1;
topN=topN-1;
pos[topP]+=1;
topS=topS-1;
if(topP!=-1)
func(n,pos,sum,arr,topN,topP,topS);
}
else if(found!=1)
func(n,pos,sum,arr,topN,topP,topS);
}
main()
{
int x,n[100],pos[100],sum[100],arr[10]={63,36,22,19,12,9,7,5,3,1},topN=-1,topP=-1,topS=-1;
cout<<"Enter a number: ";
cin>>x;
topN=topN+1;
n[topN]=x;
topP=topP+1;
pos[topP]=0;
func(n,pos,sum,arr,topN,topP,topS);
if(found==0)
cout<<"Not found any combination";
else{
cout<<"\n"<<sum[0];
for(int i=1;i<=topS;i++)
cout<<" + "<<sum[i];
}
getch();
}
Você pode copiar o código e colá-lo no seu IDE, funciona bem :-)
