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:
AUTHORS:
EXAMPLES:
We can test for whether or not a sequence is super-increasing:
sage: from sage.numerical.knapsack import Superincreasing
sage: L = [1, 2, 5, 21, 69, 189, 376, 919]
sage: seq = Superincreasing(L)
sage: seq
Super-increasing 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 super-increasing 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]
A class for super-increasing sequences.
Let be a non-empty sequence of
non-negative integers. Then
is said to be super-increasing if
each
is strictly greater than the sum of all previous values.
That is, for each
the sequence
must satisfy the property
in order to be called a super-increasing sequence, where .
If
has only one element, it is also defined to be a
super-increasing sequence.
If seq is None, then construct an empty sequence. By definition, this empty sequence is not super-increasing.
INPUT:
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
Super-increasing sequence of length 3
sage: seq = Superincreasing(list([1, 2, 5, 21, 69, 189, 376, 919])); seq
Super-increasing sequence of length 8
Comparing self to other.
TESTS:
sage: from sage.numerical.knapsack import Superincreasing
sage: L = [1, 2, 5, 21, 69, 189, 376, 919]
sage: seq = Superincreasing(L)
sage: seq == loads(dumps(seq))
True
Constructing a super-increasing sequence object from seq.
If seq is None, then construct an empty sequence. By definition, this empty sequence is not super-increasing.
INPUT:
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
Return a string representation of this super-increasing sequence object.
EXAMPLES:
sage: from sage.numerical.knapsack import Superincreasing
sage: seq = Superincreasing(); seq
An empty sequence.
sage: seq = Superincreasing([1, 3, 6]); seq
Super-increasing sequence of length 3
sage: seq = Superincreasing(list([1, 2, 5, 21, 69, 189, 376, 919])); seq
Super-increasing sequence of length 8
Return LaTeX representation of self.
EXAMPLES:
sage: from sage.numerical.knapsack import Superincreasing
sage: latex(Superincreasing())
\left[\right]
sage: seq = Superincreasing([1, 2, 5, 21, 69, 189, 376, 919])
sage: latex(seq)
<BLANKLINE>
\left[1,
2,
5,
21,
69,
189,
376,
919\right]
Determine whether or not seq is super-increasing.
If seq=None then determine whether or not self is super-increasing.
Let be a non-empty sequence of
non-negative integers. Then
is said to be super-increasing if
each
is strictly greater than the sum of all previous values.
That is, for each
the sequence
must satisfy the
property
in order to be called a super-increasing sequence, where .
If
has exactly one element, then it is also defined to be a
super-increasing sequence.
INPUT:
OUTPUT:
EXAMPLES:
By definition, an empty sequence is not super-increasing:
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 super-increasing 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 super-increasing sequence can have zero as one of its elements:
sage: L = [0, 1, 2, 4]
sage: Superincreasing(L).is_superincreasing()
True
A super-increasing sequence can be of length 1:
sage: Superincreasing([randint(0, 100)]).is_superincreasing()
True
TESTS:
The sequence must contain only integers:
sage: from sage.numerical.knapsack import Superincreasing
sage: L = [1.0, 2.1, pi, 21, 69, 189, 376, 919]
sage: Superincreasing(L).is_superincreasing()
...
TypeError: Element e (= 1.00000000000000) of seq must be a non-negative integer.
sage: L = [1, 2.1, pi, 21, 69, 189, 376, 919]
sage: Superincreasing(L).is_superincreasing()
...
TypeError: Element e (= 2.10000000000000) of seq must be a non-negative integer.
Return the largest integer in the sequence self that is less than or equal to N.
This function narrows down the candidate solution using a binary trim, similar to the way binary search halves the sequence at each iteration.
INPUT:
OUTPUT:
The largest integer in self that is less than or equal to N. If no solution exists, then return None.
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) == None
True
TESTS:
The target N must be an integer:
sage: from sage.numerical.knapsack import Superincreasing
sage: L = [2, 3, 7, 25, 67, 179, 356, 819]
sage: Superincreasing(L).largest_less_than(2.30)
...
TypeError: N (= 2.30000000000000) must be an integer.
The sequence that self represents must also be non-empty:
sage: Superincreasing([]).largest_less_than(2)
...
ValueError: seq must be a super-increasing sequence
sage: Superincreasing(list()).largest_less_than(2)
...
ValueError: seq must be a super-increasing sequence
Solving the subset sum problem for a super-increasing sequence.
Let be a non-empty sequence of
non-negative integers, and let
be non-negative. The
subset sum problem asks for a subset
all of whose
elements sum to
. This method specializes the subset sum problem
to the case of super-increasing sequences. If a solution exists, then
it is also a super-increasing sequence.
Note
This method only solves the subset sum problem for super-increasing sequences. In general, solving the subset sum problem for an arbitrary sequence is known to be computationally hard.
INPUT:
OUTPUT:
ALGORITHMS:
The algorithm used is adapted from page 355 of [HPS08].
EXAMPLES:
Solving the subset sum problem for a super-increasing 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]
TESTS:
The target N must be a non-negative integer:
sage: from sage.numerical.knapsack import Superincreasing
sage: L = [0, 1, 2, 4]
sage: Superincreasing(L).subset_sum(-6)
...
TypeError: N (= -6) must be a non-negative integer.
sage: Superincreasing(L).subset_sum(-6.2)
...
TypeError: N (= -6.20000000000000) must be a non-negative integer.
The sequence that self represents must only contain non-negative integers:
sage: L = [-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1]
sage: Superincreasing(L).subset_sum(1)
...
TypeError: Element e (= -10) of seq must be a non-negative integer.
REFERENCES:
[HPS08] | J. Hoffstein, J. Pipher, and J.H. Silverman. An Introduction to Mathematical Cryptography. Springer, 2008. |