I am already puzzling for two weeks programming a knapsack problem in C.
Since I didn't manage to get it working with structs directly, I have made a solution with an extra array. If you know how to use the structs directly, that would be great!
But the main problem is, that when I get multiple solutions with the same value, I'd want to only get the solution with the least weight.
My code till now:
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <stdbool.h>
#include <string.h>
#define TEAMS 5
#define max_players 20
typedef struct Team
{
char name [10];
int players;
bool Is_Playing;
int points;
} Team;
struct Team one = { "Ones", 12, true, 18 };
struct Team two = { "Twos", 4, true, 10 };
struct Team three = { "Threes", 5, true, 9 };
struct Team four = { "Fours", 12, true, 22 };
struct Team five = { "Fives", 8, true, 15 };
typedef struct selection_entry
{
int points;
int team;
struct selection_entry *prev;
} selection_entry;
Team *teams[TEAMS] = { &one, &two, &three, &four, &five };
int selection(int players[], const int *selection_points, size_t n,
int capacity, int **solution)
{
int i, j;
selection_entry **table;
int result;
selection_entry *head;
/* Allocate the table */
table = malloc((n + 1) * sizeof(selection_entry *));
for (i = 0; i <= n; i++) {
table[i] = malloc((capacity + 1) * sizeof(selection_entry));
}
/* Calculate the points and build chains */
for (i = 0; i <= n; i++) {
for (j = 0; j <= capacity; j++) {
if (i == 0 || j == 0) {
/* Initialising the first row or column */
table[i][j].points = 0;
table[i][j].team = 0;
table[i][j].prev = NULL;
}
else if (players[i - 1] <= j) {
/* Can add team */
if (selection_points[i - 1] + table[i - 1][j - players[i - 1]].points
> table[i - 1][j].points) {
/* Add team */
table[i][j].points = selection_points[i - 1] + table[i - 1][j - players[i - 1]].points;
table[i][j].team = i - 1;
table[i][j].prev = &table[i - 1][j - players[i - 1]];
}
else {
/* Don't add team */
table[i][j].points = table[i - 1][j].points;
table[i][j].team = table[i - 1][j].team;
table[i][j].prev = table[i - 1][j].prev;
}
}
else {
/* Don't add team */
table[i][j].points = table[i - 1][j].points;
table[i][j].team = table[i - 1][j].team;
table[i][j].prev = table[i - 1][j].prev;
}
}
}
/* Read back the solution */
*solution = calloc(n, sizeof(int));
for (i = 0, head = &table[n][capacity];
head->prev != NULL;
head = head->prev, i++) {
(*solution)[head->team] = 1;
}
result = table[n][capacity].points;
for (i = 0; i <= n; i++) {
free(table[i]);
}
free(table);
return result;
}
int GetSelectionArraySize()
{
int s=0;
for (int i = 0; i < TEAMS; i++)
{
if (teams[i]->Is_Playing)
{
s++;
}
}
return s;
}
void main()
{
int a_size = GetSelectionArraySize();
int players[a_size];
int selection_points[a_size];
int i, j=0;
for (int i = 0; i < TEAMS; i++)
{
if (teams[i]->Is_Playing)
{
players[j] = teams[i]->players;
selection_points[j] = teams[i]->points;
j++;
}
}
const int capacity = max_players;
const size_t n = sizeof(players) / sizeof(players[0]);
int *solution;
int points = selection(players, selection_points, n, capacity, &solution);
fprintf(stdout, "Value: %d\n", points);
for (i = 0; i < n; i++)
{
if (solution[i])
{
fprintf(stdout, "Team %d with %d players and %d points.\n", i, players[i], selection_points[i]);
}
}
free(solution);
}
Problems: I can't figure out why this isn't working properly and how I get it to give me the best solution (highest points but least players within the maximum specified number of players).
Sub-problem: The array-workaround annoys me, but I fail in making it work with the original arrays of structs directly...
Thank you very much in advance!!!
Kindest regards!
Ralf