Knapsack Problems¶
This module implements a number of solutions to various knapsack problems, otherwise known as linear integer programming problems. Solutions to the following knapsack problems are implemented:
Solving the subset sum problem for superincreasing sequences.
General case using Linear Programming
AUTHORS:
Minh Van Nguyen (200904): initial version
Nathann Cohen (200908): Linear Programming version
Definition of Knapsack problems¶
You have already had a knapsack problem, so you should know, but in case you do not, a knapsack problem is what happens when you have hundred of items to put into a bag which is too small, and you want to pack the most useful of them.
When you formally write it, here is your problem:
Your bag can contain a weight of at most \(W\).
Each item \(i\) has a weight \(w_i\).
Each item \(i\) has a usefulness \(u_i\).
You then want to maximize the total usefulness of the items you will store into your bag, while keeping sure the weight of the bag will not go over \(W\).
As a linear program, this problem can be represented this way (if you define \(b_i\) as the binary variable indicating whether the item \(i\) is to be included in your bag):
(For more information, see the Wikipedia article Knapsack_problem)
Examples¶
If your knapsack problem is composed of three items (weight, value) defined by (1,2), (1.5,1), (0.5,3), and a bag of maximum weight 2, you can easily solve it this way:
sage: from sage.numerical.knapsack import knapsack
sage: knapsack( [(1,2), (1.5,1), (0.5,3)], max=2)
[5.0, [(1, 2), (0.500000000000000, 3)]]
Superincreasing sequences¶
We can test for whether or not a sequence is superincreasing:
sage: from sage.numerical.knapsack import Superincreasing
sage: L = [1, 2, 5, 21, 69, 189, 376, 919]
sage: seq = Superincreasing(L)
sage: seq
Superincreasing sequence of length 8
sage: seq.is_superincreasing()
True
sage: Superincreasing().is_superincreasing([1,3,5,7])
False
Solving the subset sum problem for a superincreasing sequence and target sum:
sage: L = [1, 2, 5, 21, 69, 189, 376, 919]
sage: Superincreasing(L).subset_sum(98)
[69, 21, 5, 2, 1]

class
sage.numerical.knapsack.
Superincreasing
(seq=None)¶ Bases:
sage.structure.sage_object.SageObject
A class for superincreasing sequences.
Let \(L = (a_1, a_2, a_3, \dots, a_n)\) be a nonempty sequence of nonnegative integers. Then \(L\) is said to be superincreasing if each \(a_i\) is strictly greater than the sum of all previous values. That is, for each \(a_i \in L\) the sequence \(L\) must satisfy the property
\[a_i > \sum_{k=1}^{i1} a_k\]in order to be called a superincreasing sequence, where \(L \geq 2\). If \(L\) has only one element, it is also defined to be a superincreasing sequence.
If
seq
isNone
, then construct an empty sequence. By definition, this empty sequence is not superincreasing.INPUT:
seq
– (default:None
) a nonempty sequence.
EXAMPLES:
sage: from sage.numerical.knapsack import Superincreasing sage: L = [1, 2, 5, 21, 69, 189, 376, 919] sage: Superincreasing(L).is_superincreasing() True sage: Superincreasing().is_superincreasing([1,3,5,7]) False sage: seq = Superincreasing(); seq An empty sequence. sage: seq = Superincreasing([1, 3, 6]); seq Superincreasing sequence of length 3 sage: seq = Superincreasing(list([1, 2, 5, 21, 69, 189, 376, 919])); seq Superincreasing sequence of length 8

is_superincreasing
(seq=None)¶ Determine whether or not
seq
is superincreasing.If
seq=None
then determine whether or notself
is superincreasing.Let \(L = (a_1, a_2, a_3, \dots, a_n)\) be a nonempty sequence of nonnegative integers. Then \(L\) is said to be superincreasing if each \(a_i\) is strictly greater than the sum of all previous values. That is, for each \(a_i \in L\) the sequence \(L\) must satisfy the property
\[a_i > \sum_{k=1}^{i1} a_k\]in order to be called a superincreasing sequence, where \(L \geq 2\). If \(L\) has exactly one element, then it is also defined to be a superincreasing sequence.
INPUT:
seq
– (default:None
) a sequence to test
OUTPUT:
If
seq
isNone
, then testself
to determine whether or not it is superincreasing. In that case, returnTrue
ifself
is superincreasing;False
otherwise.If
seq
is notNone
, then testseq
to determine whether or not it is superincreasing. ReturnTrue
ifseq
is superincreasing;False
otherwise.
EXAMPLES:
By definition, an empty sequence is not superincreasing:
sage: from sage.numerical.knapsack import Superincreasing sage: Superincreasing().is_superincreasing([]) False sage: Superincreasing().is_superincreasing() False sage: Superincreasing().is_superincreasing(tuple()) False sage: Superincreasing().is_superincreasing(()) False
But here is an example of a superincreasing sequence:
sage: L = [1, 2, 5, 21, 69, 189, 376, 919] sage: Superincreasing(L).is_superincreasing() True sage: L = (1, 2, 5, 21, 69, 189, 376, 919) sage: Superincreasing(L).is_superincreasing() True
A superincreasing sequence can have zero as one of its elements:
sage: L = [0, 1, 2, 4] sage: Superincreasing(L).is_superincreasing() True
A superincreasing sequence can be of length 1:
sage: Superincreasing([randint(0, 100)]).is_superincreasing() True

largest_less_than
(N)¶ Return the largest integer in the sequence
self
that is less than or equal toN
.This function narrows down the candidate solution using a binary trim, similar to the way binary search halves the sequence at each iteration.
INPUT:
N
– integer; the target value to search for.
OUTPUT:
The largest integer in
self
that is less than or equal toN
. If no solution exists, then returnNone
.EXAMPLES:
When a solution is found, return it:
sage: from sage.numerical.knapsack import Superincreasing sage: L = [2, 3, 7, 25, 67, 179, 356, 819] sage: Superincreasing(L).largest_less_than(207) 179 sage: L = (2, 3, 7, 25, 67, 179, 356, 819) sage: Superincreasing(L).largest_less_than(2) 2
But if no solution exists, return
None
:sage: L = [2, 3, 7, 25, 67, 179, 356, 819] sage: Superincreasing(L).largest_less_than(1) is None True

subset_sum
(N)¶ Solving the subset sum problem for a superincreasing sequence.
Let \(S = (s_1, s_2, s_3, \dots, s_n)\) be a nonempty sequence of nonnegative integers, and let \(N \in \ZZ\) be nonnegative. The subset sum problem asks for a subset \(A \subseteq S\) all of whose elements sum to \(N\). This method specializes the subset sum problem to the case of superincreasing sequences. If a solution exists, then it is also a superincreasing sequence.
Note
This method only solves the subset sum problem for superincreasing sequences. In general, solving the subset sum problem for an arbitrary sequence is known to be computationally hard.
INPUT:
N
– a nonnegative integer.
OUTPUT:
A nonempty subset of
self
whose elements sum toN
. This subset is also a superincreasing sequence. If no such subset exists, then return the empty list.
ALGORITHMS:
The algorithm used is adapted from page 355 of [HPS2008].
EXAMPLES:
Solving the subset sum problem for a superincreasing sequence and target sum:
sage: from sage.numerical.knapsack import Superincreasing sage: L = [1, 2, 5, 21, 69, 189, 376, 919] sage: Superincreasing(L).subset_sum(98) [69, 21, 5, 2, 1]

sage.numerical.knapsack.
knapsack
(seq, binary=True, max=1, value_only=False, solver=None, verbose=0)¶ Solves the knapsack problem
For more information on the knapsack problem, see the documentation of the
knapsack module
or the Wikipedia article Knapsack_problem.INPUT:
seq
– Two different possible types:A sequence of tuples
(weight, value, something1, something2, ...)
. Note that only the first two coordinates (weight
andvalues
) will be taken into account. The rest (if any) will be ignored. This can be useful if you need to attach some information to the items.A sequence of reals (a value of 1 is assumed).
binary
– When set toTrue
, an item can be taken 0 or 1 time. When set toFalse
, an item can be taken any amount of times (while staying integer and positive).max
– Maximum admissible weight.value_only
– When set toTrue
, only the maximum useful value is returned. When set toFalse
, both the maximum useful value and an assignment are returned.solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the documentation of classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
OUTPUT:
If
value_only
is set toTrue
, only the maximum useful value is returned. Else (the default), the function returns a pair[value,list]
, wherelist
can be of two types according to the type ofseq
:The list of tuples \((w_i, u_i, ...)\) occurring in the solution.
A list of reals where each real is repeated the number of times it is taken into the solution.
EXAMPLES:
If your knapsack problem is composed of three items
(weight, value)
defined by(1,2), (1.5,1), (0.5,3)
, and a bag of maximum weight \(2\), you can easily solve it this way:sage: from sage.numerical.knapsack import knapsack sage: knapsack( [(1,2), (1.5,1), (0.5,3)], max=2) [5.0, [(1, 2), (0.500000000000000, 3)]] sage: knapsack( [(1,2), (1.5,1), (0.5,3)], max=2, value_only=True) 5.0
Besides weight and value, you may attach any data to the items:
sage: from sage.numerical.knapsack import knapsack sage: knapsack( [(1, 2, 'spam'), (0.5, 3, 'a', 'lot')]) [3.0, [(0.500000000000000, 3, 'a', 'lot')]]
In the case where all the values (usefulness) of the items are equal to one, you do not need embarrass yourself with the second values, and you can just type for items \((1,1), (1.5,1), (0.5,1)\) the command:
sage: from sage.numerical.knapsack import knapsack sage: knapsack([1,1.5,0.5], max=2, value_only=True) 2.0