1/*-------------------------------------------------------------------------
2 *
3 * knapsack.c
4 * Knapsack problem solver
5 *
6 * Given input vectors of integral item weights (must be >= 0) and values
7 * (double >= 0), compute the set of items which produces the greatest total
8 * value without exceeding a specified total weight; each item is included at
9 * most once (this is the 0/1 knapsack problem). Weight 0 items will always be
10 * included.
11 *
12 * The performance of this algorithm is pseudo-polynomial, O(nW) where W is the
13 * weight limit. To use with non-integral weights or approximate solutions,
14 * the caller should pre-scale the input weights to a suitable range. This
15 * allows approximate solutions in polynomial time (the general case of the
16 * exact problem is NP-hard).
17 *
18 * Copyright (c) 2017-2019, PostgreSQL Global Development Group
19 *
20 * IDENTIFICATION
21 * src/backend/lib/knapsack.c
22 *
23 *-------------------------------------------------------------------------
24 */
25#include "postgres.h"
26
27#include <math.h>
28#include <limits.h>
29
30#include "lib/knapsack.h"
31#include "miscadmin.h"
32#include "nodes/bitmapset.h"
33#include "utils/builtins.h"
34#include "utils/memutils.h"
35
36/*
37 * DiscreteKnapsack
38 *
39 * The item_values input is optional; if omitted, all the items are assumed to
40 * have value 1.
41 *
42 * Returns a Bitmapset of the 0..(n-1) indexes of the items chosen for
43 * inclusion in the solution.
44 *
45 * This uses the usual dynamic-programming algorithm, adapted to reuse the
46 * memory on each pass (by working from larger weights to smaller). At the
47 * start of pass number i, the values[w] array contains the largest value
48 * computed with total weight <= w, using only items with indices < i; and
49 * sets[w] contains the bitmap of items actually used for that value. (The
50 * bitmapsets are all pre-initialized with an unused high bit so that memory
51 * allocation is done only once.)
52 */
53Bitmapset *
54DiscreteKnapsack(int max_weight, int num_items,
55 int *item_weights, double *item_values)
56{
57 MemoryContext local_ctx = AllocSetContextCreate(CurrentMemoryContext,
58 "Knapsack",
59 ALLOCSET_SMALL_SIZES);
60 MemoryContext oldctx = MemoryContextSwitchTo(local_ctx);
61 double *values;
62 Bitmapset **sets;
63 Bitmapset *result;
64 int i,
65 j;
66
67 Assert(max_weight >= 0);
68 Assert(num_items > 0 && item_weights);
69
70 values = palloc((1 + max_weight) * sizeof(double));
71 sets = palloc((1 + max_weight) * sizeof(Bitmapset *));
72
73 for (i = 0; i <= max_weight; ++i)
74 {
75 values[i] = 0;
76 sets[i] = bms_make_singleton(num_items);
77 }
78
79 for (i = 0; i < num_items; ++i)
80 {
81 int iw = item_weights[i];
82 double iv = item_values ? item_values[i] : 1;
83
84 for (j = max_weight; j >= iw; --j)
85 {
86 int ow = j - iw;
87
88 if (values[j] <= values[ow] + iv)
89 {
90 /* copy sets[ow] to sets[j] without realloc */
91 if (j != ow)
92 {
93 sets[j] = bms_del_members(sets[j], sets[j]);
94 sets[j] = bms_add_members(sets[j], sets[ow]);
95 }
96
97 sets[j] = bms_add_member(sets[j], i);
98
99 values[j] = values[ow] + iv;
100 }
101 }
102 }
103
104 MemoryContextSwitchTo(oldctx);
105
106 result = bms_del_member(bms_copy(sets[max_weight]), num_items);
107
108 MemoryContextDelete(local_ctx);
109
110 return result;
111}
112