74 lines
2.0 KiB
C
74 lines
2.0 KiB
C
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <sys/param.h>
|
|
|
|
typedef struct item {
|
|
int value, weight;
|
|
} Item;
|
|
|
|
Item * initializeList (int size) {
|
|
int i;
|
|
Item *list = malloc(size * sizeof(Item));
|
|
|
|
for (i = 0; i < size; i++)
|
|
scanf(" %d", &list[i].weight);
|
|
for (i = 0; i < size; i++)
|
|
scanf(" %d", &list[i].value);
|
|
return list;
|
|
}
|
|
|
|
int ** initializeTable (Item *list, int size, int capacity) {
|
|
int i, j, **results = malloc(++size * sizeof(int*));
|
|
|
|
results[0] = calloc(++capacity, sizeof(int));
|
|
for (i = 1; i < size; i++) {
|
|
results[i] = malloc(capacity * sizeof(int));
|
|
for (j = 0; j < capacity; j++)
|
|
results[i][j] = (list[i - 1].weight > j) ? results[i - 1][j] : MAX(results[i - 1][j], list[i - 1].value + results[i - 1][j - list[i - 1].weight]);
|
|
}
|
|
return results;
|
|
}
|
|
|
|
void outputSelection (Item *list, int **results, int size, int capacity) {
|
|
int i = -1, total = 0, *index = malloc(size * sizeof(int));
|
|
|
|
while (size > 0) {
|
|
if (results[size][capacity] != results[size - 1][capacity]) {
|
|
capacity -= list[size - 1].weight;
|
|
total += list[size - 1].value;
|
|
index[++i] = size - 1;
|
|
}
|
|
free(results[size--]);
|
|
}
|
|
free(*results);
|
|
free(results);
|
|
|
|
while (i >= 0) {
|
|
printf("Item: %-5d Valor: %5d Peso: %5d Razão: %f\n",
|
|
index[i] + 1, list[index[i]].value, list[index[i]].weight,
|
|
(float) list[index[i]].value / list[index[i]].weight);
|
|
i--;
|
|
}
|
|
free(list);
|
|
free(index);
|
|
|
|
printf("Capacidade restante da mochila: %d\n", capacity);
|
|
printf("Valor total armazenado: %d\n", total);
|
|
}
|
|
|
|
void dynamicKnapsack (Item *list, int size) {
|
|
int capacity;
|
|
|
|
scanf(" %d", &capacity);
|
|
printf("Capacidade da mochila: %d\nConteúdos:\n", capacity);
|
|
outputSelection(list, initializeTable(list, size, capacity), size, capacity);
|
|
}
|
|
|
|
int main () {
|
|
int size;
|
|
|
|
scanf(" %d", &size);
|
|
dynamicKnapsack(initializeList(size), size);
|
|
return 0;
|
|
}
|