Angel Laguna - combinación de cajas con mayor cantidad de dinero y que no sobrepase la capacidad de la bolsa.

reto8.c

#include <stdio.h>
#include <stdlib.h>

struct Box {
    int value;
    int weight;
};

struct PouchGrinch {
    struct Box *box;
    int boxNumber;
    int capacity;
};

int MAX(int a, int b) {
    return a >= b ? a : b;
}

void insert_box(struct PouchGrinch *pg, int value, int weight, int indice){
    pg->box[indice].value = value;
    pg->box[indice].weight = weight;
}

void showBoxes(struct PouchGrinch pg){
    for(int i = 0; i < pg.boxNumber; i++) {
        printf("{caja %d : $ %d\t usd, %dkg }\n", i+1, pg.box[i].value, pg.box[i].weight);
    }
}

void grinch_bag_in_action(struct PouchGrinch pg) {
    int **m;
    int size     = pg.boxNumber;
    int capacity = pg.capacity ;
    int c_m;
    int c_capacity;
    int pos = 0;

    m = (int **)malloc ((size+1)*sizeof(int *));
    for (int i = 0; i < size+1; i++)  {
        m[i] = (int *) malloc ((capacity+1)*sizeof(int));
    }

    for(int i = 0; i <= capacity; i++){
        m[0][i] = 0;
    }

    for (int i = 1; i <= size; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (pg.box[i - 1].weight > j) {
                m[i][j] = m[i-1][j];
            }else{
                m[i][j] = MAX(m[i-1][j], m[i-1][j - pg.box[i-1].weight] + pg.box[i-1].value);
            }    
        }
    }

    c_m        = m[size][capacity];
    c_capacity = capacity;
    
    struct PouchGrinch c_pg;
    c_pg.box       = calloc(pg.boxNumber, sizeof(struct Box));
    c_pg.boxNumber = pg.boxNumber;
    c_pg.capacity  = 150;

    for (int i = size; i > 0  &&  c_m > 0; i--) {
        if (c_m != m[i-1][c_capacity]) {
            c_pg.box[pos] = pg.box[i-1];
            c_m           = c_m - pg.box[i-1].value;
            c_capacity    = c_capacity - pg.box[i-1].weight;
            pos++;
        }
    }

    c_pg.boxNumber = pos;

    printf("\n");
    showBoxes(c_pg);

}

int main(int argc, char *argv[]) {

    int boxNumber = 5;
    struct PouchGrinch pg;

    pg.box       = calloc(boxNumber, sizeof(struct Box));
    pg.boxNumber = 5;
    pg.capacity  = 150;
    

    insert_box(&pg, 100, 40,  0);
    insert_box(&pg, 20,  10,  1);
    insert_box(&pg, 40,  120, 2);
    insert_box(&pg, 20,  20,  3);
    insert_box(&pg, 10,  10,  4);

    showBoxes(pg);

    grinch_bag_in_action(pg);  

    return EXIT_SUCCESS;
}