[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] Re: [obm-l] recurs�o



bom, a def. do seu problema cont�m um erro, voc� est� pedindo para retornar uma combina��o de n �ndices, ou seja s� existe uma!
mas tudo bem, acho que voc� tem a liberdade de usar quantos elementos quiser do vetor p.
 
pense que voc� tem um vetor r com n elementos.
 
 
void mochila(int P, int* p, int* r, int i, int n)
{
    if ( i < n )
    {
        /* coloca o i'�simo item na mochila */
        r[i] = 1;
        /* o peso adicional que deve ser colocado � P - p[i] */
       mochila( P - p[i], p, r, i + 1, n );
   
        /* n�o coloca o i'�simo item na mochila */
       r[i] = 0;
       mochila( P, p, r, i + 1, n );
    }
    else if ( P == 0 )
    {
        /* Imprime os itens inseridos */
        for ( int j = 0; j < n; j++ )
        {
            printf( "Combina��o encontrada: \n" );
            if ( r[j] )
                printf( "p%d ", j );
        }
    }
 
    return;
}
 
chame a fun��o dessa forma:
 
mochila( P, p, r, 0, n );
 
pode haver algum erro pq eu fiz sem testar, mas deve rodar.
----- Original Message -----
Sent: Wednesday, May 07, 2003 9:40 AM
Subject: [obm-l] recurs�o

algu�m pode me ajudar com o seguinte problema? preciso de uma id�ia de como fazer!

Entradas:
> - um inteiro n;
> - um vetor de ordem n de inteiros de pesos (p[n]);
> - um inteiro P;
> Tenho uma mochila que carrega at� P quilos, e voce tem n itens de
> pesos p1, p2, p3,...,pn. Tenho que fazer um programa para achar todas as  combinacoes de itens i1,i2,...,in tal que a soma de seus pesos seja igual a P, caso nao encontre nenhuma combinacao, tenho que mostrar que n�o encontrei nenhuma combina��o

> o problema deve ser feito se utilizando de uma funcao recursiva 

Se algu�m puder me ajudar agrade�o muito,

Abra�os a todos!



Yahoo! Mail
O melhor e-mail gratuito da internet: 6MB de espa�o, antiv�rus, acesso POP3, filtro contra spam.