• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

| Blasted |

Knapsack

5 mensagens neste tópico

Saudações!

Bem, tenho um problema para resolver que consiste no seguinte. Dado um conjunto de números como o seguinte:

1200
1300
2450
780
780
1345
4010

arranjar a forma optimizada de agrupar os vários valores de forma a não ultrapassar um determinado valor, neste caso seria 6100.

Segundo o que pesquisei por aqui isto assemelha-se a um problema do género knapsack.

Encontrei isto: http://www.portugal-a-programar.pt/forums/topic/0-find-topic/?do=findComment&comment=266948

Acabei por entender razoavelmente o método, mas não estou a conseguir fazer a matriz como é explicado no método do Warrior (ver link acima).

Alguém me pode ajudar?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso é exactamente knapsack, tal como expliquei nesse link, não posso explicar muito mais sem seres mais explicito.

Eu neste momento estou de férias e demoro a regressar, mas se colocares uma dúvida mais concreta alguém te há de responder.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já encontrei varios problemas deste tipo e tambem  já percebi o metodo de resolucao graças ao post do Warrior mas não consigo implementar. Será que alguem podia colocar o codigo mesmo do algoritmo nem que fosse so para a resolucao daquele problema ali em cima do blasted, de certeza que depois ja conseguia perceber a ideia e aplicar a outros.

Tambem ja pesquisei por exemplos na net, mas acho que quanto mais vejo mais confuso fico :/

Cumps :P

ps: sim sou um grande escavador, mas a minha duvida pareceu ser a mesma do blasted  :biggrin:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Queres saber apenas o peso maximo abaixo de um limite?

int numeros[MAXN], N; // numeros

char bag[MAXVALOR]; 

// init array bag a 0

bag[0] = 1; // peso 0 é sempre possível : não usar nada

for (i = 0 ; i < N ; i++) // percorrer os N números
     for (peso = MAXVAL - numeros[i] ; peso >= 0 ; peso-- )
           if ( bag[peso] )
                 bag[peso + numeros[i] ] = 1;  // se com i-1 números era possível ter uma soma igual a "peso", então 
                                               // adicionando este passa a poder ter-se "peso+numeros[i]"

for (i = MAXVAL ; bag[i] == 0 ; i-- )
    ;
// i tem a soma máxima possível

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora