src/dfs.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <stdlib.h>
#include "dfs.h"
#include "structs.h"
#include "common.h"

struct front_item * rec(struct data * d, int i, struct item * it) {
  if(i == d->N) {
    return new_front_item(it->p, it->w, NULL, NULL);
  }

  // Go left (select item)
  it->p += d->items[i].p;
  it->w += d->items[i].w;
  struct front_item * f1 = rec(d, i+1, it);
  it->p -= d->items[i].p;
  it->w -= d->items[i].w;

  // Go right (do not select item)
  struct front_item * f2 = rec(d, i+1, it);

  // Merge
  struct front_item * f1_end = f1;
  for(;f1_end->next!=NULL; f1_end = f1_end->next);
  f1_end->next = f2;
  f2->prev = f1_end;
  
  return f1;
}

struct front_item * dfs(struct data * d) {
  struct item * it = (struct item *)malloc(sizeof(struct item));
  it->p = 0;
  it->w = 0;

  return rec(d, 0, it);
}