PostgreSQL Source Code git master
Functions
knapsack.c File Reference
#include "postgres.h"
#include <math.h>
#include <limits.h>
#include "lib/knapsack.h"
#include "nodes/bitmapset.h"
#include "utils/memutils.h"
Include dependency graph for knapsack.c:

Go to the source code of this file.

Functions

Bitmapset *  DiscreteKnapsack (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 
)

Definition at line 52 of file knapsack.c.

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

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

Referenced by consider_groupingsets_paths().

AltStyle によって変換されたページ (->オリジナル) /