Mochila_PD.c

Mochila_PD.c

#include <stdio.h>

#define MAX(x,y)    x>y?x:y

int pd[100][100];

int mochila(int n, int cap, int peso[], int valor[])
{
    int i;
    int j;
    
    for (i = 1; i <= n; i++)
    {
        for(j = 0; j <= cap; j++)
        {
            if(peso[i-1]>j)
            {
                pd[i][j] = pd[i-1][j];
            }
            else
            {
                pd[i][j] = MAX(pd[i-1][j], (pd[i-1][j-peso[i-1]] + valor[i-1]));
            }
        }
    }
    
    return pd[n][cap];    
}

void recovery(int n, int cap, int peso[], int valor[], int val)
{
    int i = n;
    int j = cap;
    
    while(pd[i][j])
    {
        if(val != pd[--i][j])
        {
            printf("Obj: %i\n",i+1);
            j -= peso[i];
            val = pd[i][j];
        }
    }
    return;
}

int main(void)
{
    int n, cap, i;
    
    scanf("%d %d", &n, &cap);
    
    int peso[n]; 
    int valor[n];
    
    for(i = 0; i < n; i++)
        scanf("%d %d", &peso[i], &valor[i]);
    int ans = mochila(n, cap, peso, valor);
    printf("Resposta = %d\n", ans);
    
    recovery(n,cap,peso,valor,ans);
    
    getchar();
    getchar();
    getchar();
}
//Exemplo de INPUT: 
//  5
//  7
//  5
//  15
//  8
//  9
//  3
//  20
//  4
//  10
//  1
//  17