Código para Combinação em Pascal

[RBon1 0]

Olá !

Por favor, eu estou tentando escrever um programinha simples que, a partir de um conjunto definido A, de m números reais, me permita encontrar um subconjunto B, de n elementos, onde a soma desses n elementos de B seja menor ou igual a um dado valor x, para o maior n possível.

Por exemplo: suponha que A={5,2,1,3,15,75,10,20,4} e x=40. O objetivo do programa é somar n (maior possível) elementos de A (apresentando-os, ao final, como o subconjunto B ), de forma que o resultado dessa soma seja menor ou igual a x.

Para o conjunto A apresentado o resultado obtido seria B={5,2,1,3,15,10,4}; pois embora para B={5,15,20} a soma dos elementos também seja igual a x, no primeiro caso n=7, e no segundo n=3.

Caso a minha exposição do problema não esteja clara, vou esclarecer um pouco mais:

Eu vou ter uma matriz A[1...100] (não serão necessariamente 100 elementos para A, digamos que entrando com o valor "0" a inserção de dados é interrompida, pois todos os elementos serão números reais positivos). Durante a execução do programa eu vou entrar com os valores para essa matriz, de forma que, levando-se em conta o conjunto que eu usei lá em cima, A[1]=5, A[2]=2...

Eu preciso somar todas as combinações desses elementos (A[1]+A[2], A[1]+A[2]+A[3]... A[3]+A[4]+A[5]+A[6]+A[7]...), até encontrar as somas que se igualem ou se aproximem (sem exceder) um valor x dado (para o exemplo em questão, 40). Embora eu tenha dito que o objetivo seria encontrar uma soma que precise do maior número possível de elementos, essa quantidade em si é secundária pois o que eu preciso saber é quais foram os elementos utilizados para compô-la. Nesse exemplo, como o subconjunto encontrado é B, a resposta que vai me interessar e é o que de fato eu vou precisar saber, é: A[1], A[2], A[3], A[4], A[5], A[7], A[9] (para esclarecer: não me basta saber que eu tive que somar 5+2+1+3+15+10+4 para obter 40, eu preciso saber que esse 5 é o A[1], que o 10 é o A[6], enfim, preciso saber quais os índices da matriz que foram utilizados, e qual a soma alcançada).

Seria interessante que fosse exibido mais de um subconjunto, para que não seja necessário "apagar" o primeiro subconjunto encontrado para que se continue buscando por outros (ah sim ! uma vez que eu tenha encontrado aquele subconjunto B, com os elementos restantes eu vou precisar do C, D... quantos forem possíveis).

Será que alguém pode me fornecer um código simples que execute essa tarefa ?... por favor... um algoritmo também ajudaria bastante, pois eu realmente gostaria de entender como esse negócio vai funcionar...

[quitZAUMMM 18]

Nossa cara da pra fazer uma história com seu post hehe(bom brincadeiras a parte!)

entaum tente implementar isso, escreva no papel como acha q vai ser e tal, utilize diagrama de blocos se necessario!

as duvidas iram surgindo e voce vai postando elas, beleza?! bom é isso!

 

[]'s

[_Isis_ 202]

Mas pessoa... Se o propósito é achar um conjunto máximo, qualquer combinação dos elementos desse conjunto ainda tá valendo para o problema,não?

 

Até onde eu entendi,é questão de ir somando sempre os elementos mínimos da entrada.

[RBon1 0]

Putz... faltaram umas informações importantes: o x do problema (não genérico, é o "x" mesmo, aquele "40" do exemplo) geralmente vai ser 4483 (e porque isso ? porque esse é o espaço que eu tenho disponível, em MB, para gravar em um dvd).

Sobre a sua sugestão, import java.Isis, a princípio é a coisa mais lógica a se fazer, claro, mas o que eu quero mesmo é otimizar o meu processo de arquivamento em mídia (traduzindo: a grana está curta e eu quero aproveitar cada MB possivel na hora de gravar um dvd !... http://forum.imasters.com.br/public/style_emoticons/default/cry.gif ).

Hoje mesmo, eu tinha uma sequência de arquivos para serem gravados em dvd que totalizavam 4380 MB... eu iria perder 104 MB nesse dvd, pois o menor arquivo que eu tinha era de 150 MB. O que eu fiz foi justamente aplicar a sua sugestão, que para esse caso em particular (?) deu certo; minha sequência de arquivos ficou toda comprometida mas consegui uma combinação que totalizou 4480 MB.

O fato é eu devo ter exposto mal o meu problema, pois não necessariamente o resultado pretendido vai ser o subconjunto de maior "n", o que eu quero mesmo é chegar o mais perto possível de "x" (ou seja, 4483). Essa tarde, por exemplo, eu estava com 104 MB sobrando que não me permitiam gravar mais nada, mas daí eu excluí dois arquivos de uns 155 MB cada e com os 410 MB que eu fiquei pude gravar dois arquivos de uns 200 MB cada.

É esse trabalho que o programa tem que fazer...

Sobrou 100 ? Não há espaço suficiente para gravar mais nenhum arquivo. Nesse caso ele tem que verificar como eliminar alguns elementos até então selecionados para substituí-los com outros maiores, que aproveitando o espaço que já estava livre poderão ser então gravados.

Ah ! e obrigado pelo post, import java.Isis !

E quitZAUMMM... a minha cabeça começa a dar nó só de lembrar naquele negócio de ordenação shell... porque acho que uma ordenação deve ser coisa básica e inicial aqui, né não ?... Mas valeu também.

[_Isis_ 202]

não necessariamente o resultado pretendido vai ser o subconjunto de maior "n", o que eu quero mesmo é chegar o mais perto possível de "x"

 

Se você não consegue nem formular o problema pra você mesmo...

 

Por favor, eu estou tentando escrever um programinha simples que, a partir de um conjunto definido A, de m números reais, me permita encontrar um subconjunto B, de n elementos, onde a soma desses n elementos de B seja menor ou igual a um dado valor x, para o maior n possível.

 

Criatura...lê meu post de novo. Pegando os mínimos você vai chegar próximo a x com o maior n possível.

 

 

eu iria perder 104 MB nesse dvd, pois o menor arquivo que eu tinha era de 150 MB

 

Comprima. 7z ou Bzip2 fazem isso.

 

 

Faz um exercício aí: pega um pedaço de papel e escreve esse problema em 3 linhas e de forma clara. Daí posta de novo.

[RBon1 0]

Ai meu Deus...

Primeiro, compactar não é uma opção... e depois, olha só, se eu tiver 8 arquivos com os seguintes tamanhos: 5-7-8-9-10-10-10-11 MB (m=8), e quiser gravá-los numa mídia de 50 MB (x=50), pegando os mínimos eu iria obter um n=6 (e o meu subconjunto seria 5-7-8-9-10-10). Mas desse jeito o total dá 49 MB, pode parecer bom, e até poderia ser uma opção, mas eu queria que o resultado apresentado fosse esse: 9-10-10-10-11 (x é mais importante do que n... http://forum.imasters.com.br/public/style_emoticons/default/cry.gif ).

Para poucos elementos assim fica fácil enxergar o que é melhor fazer, mas quando a história envolve centenas de arquivos daí só no olho não dá...

Quando eu jogo todos os arquivos em um diretório para selecionar os que serão gravados, claro que eu ordeno pelo tamanho e seleciono até o limite da mídia com shift pressionado... mas quando chega pertinho do limite é que aparece o problema... aqueles poucos MB que fatalmente ficam sobrando só dão dor de cabeça, porque aí eu tenho que descobrir quais arquivos dessa minha seleção inicial eu vou ter que deletar (geralmente 3 ou 4), para no lugar poder gravar alguns arquivos maiores (geralmente 2 ou 3) de forma que o espaço que sobre na mídia seja menor do que aquele que sobra gravando apenas os menores aquivos.

Chorar vale ?...

http://forum.imasters.com.br/public/style_emoticons/default/cry.gif

[RBon1 0]

Se for pra dizer em (quase) 3 linhas, é isso:

"A partir de uma lista com o tamanho de centenas de arquivos, eu quero obter uma outra mostrando o maior número de arquivos que eu posso gravar em mídia, de forma que o desperdício de espaço nessa mídia seja mínimo (sendo que o aproveitamento de espaço deve ser considerado prioritário)."

[_Isis_ 202]

Cara,ou você pega os mínimos ou os maximos.Decida-se.

 

Meça o espaço disponível e vá pegando os máximos até que o primeiro arquivo da fila não caiba.

Exclua esse arquivo da fila e continue pegando os máximos até que aconteca de novo.

 

Fazer um programa caseiro com IA não é uma opção.