PostgreSQL Source Code git master
Loading...
Searching...
No Matches
knapsack.h File Reference
#include "nodes/bitmapset.h"
Include dependency graph for knapsack.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

BitmapsetDiscreteKnapsack (int max_weight, int num_items, int *item_weights, double *item_values)
 

Function Documentation

◆ DiscreteKnapsack()

Bitmapset * DiscreteKnapsack ( int  max_weight,
int  num_items,
int item_weights,
double item_values 
)
extern

Definition at line 51 of file knapsack.c.

53{
55 "Knapsack",
58 double *values;
60 Bitmapset *result;
61 int i,
62 j;
63
64 Assert(max_weight >= 0);
65 Assert(num_items > 0 && item_weights);
66
67 values = palloc((1 + max_weight) * sizeof(double));
68 sets = palloc((1 + max_weight) * sizeof(Bitmapset *));
69
70 for (i = 0; i <= max_weight; ++i)
71 {
72 values[i] = 0;
73 sets[i] = bms_make_singleton(num_items);
74 }
75
76 for (i = 0; i < num_items; ++i)
77 {
78 int iw = item_weights[i];
79 double iv = item_values ? item_values[i] : 1;
80
81 for (j = max_weight; j >= iw; --j)
82 {
83 int ow = j - iw;
84
85 if (values[j] <= values[ow] + iv)
86 {
87 /* copy sets[ow] to sets[j] without realloc */
88 if (j != ow)
90
92
93 values[j] = values[ow] + iv;
94 }
95 }
96 }
97
99
100 result = bms_del_member(bms_copy(sets[max_weight]), num_items);
101
103
104 return result;
105}
Bitmapset * bms_replace_members(Bitmapset *a, const Bitmapset *b)
Definition bitmapset.c:971
Bitmapset * bms_make_singleton(int x)
Definition bitmapset.c:216
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition bitmapset.c:867
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition bitmapset.c:814
Bitmapset * bms_copy(const Bitmapset *a)
Definition bitmapset.c:122
static Datum values[MAXATTR]
Definition bootstrap.c:155
#define Assert(condition)
Definition c.h:873
int j
Definition isn.c:78
int i
Definition isn.c:77
void * palloc(Size size)
Definition mcxt.c:1387
MemoryContext CurrentMemoryContext
Definition mcxt.c:160
void MemoryContextDelete(MemoryContext context)
Definition mcxt.c:472
#define AllocSetContextCreate
Definition memutils.h:129
#define ALLOCSET_SMALL_SIZES
Definition memutils.h:170
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition palloc.h:124
static int fb(int x)

References ALLOCSET_SMALL_SIZES, AllocSetContextCreate, Assert, bms_add_member(), bms_copy(), bms_del_member(), bms_make_singleton(), bms_replace_members(), CurrentMemoryContext, fb(), i, j, MemoryContextDelete(), MemoryContextSwitchTo(), palloc(), and values.

Referenced by consider_groupingsets_paths().