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 super-increasing sequences.

AUTHORS:

  • Minh Van Nguyen (2009-04): initial version

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]
class sage.numerical.knapsack.Superincreasing(seq=None)

A class for super-increasing sequences.

Let L = (a_1, a_2, a_3, \dots, a_n) be a non-empty sequence of non-negative integers. Then L is said to be super-increasing 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}^{i-1} a_k

in order to be called a super-increasing sequence, where |L| \geq 2. If L 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:

  • seq – (default: None) a non-empty 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
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
__cmp__(other)

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
__init__(seq=None)

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:

  • seq – (default: None) a non-empty 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
__repr__()

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
__weakref__
list of weak references to the object (if defined)
_latex_()

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]
is_superincreasing(seq=None)

Determine whether or not seq is super-increasing.

If seq=None then determine whether or not self is super-increasing.

Let L = (a_1, a_2, a_3, \dots, a_n) be a non-empty sequence of non-negative integers. Then L is said to be super-increasing 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}^{i-1} a_k

in order to be called a super-increasing sequence, where |L| \geq 2. If L has exactly one element, then it is also defined to be a super-increasing sequence.

INPUT:

  • seq – (default: None) a sequence to test

OUTPUT:

  • If seq is None, then test self to determine whether or not it is super-increasing. In that case, return True if self is super-increasing; False otherwise.
  • If seq is not None, then test seq to determine whether or not it is super-increasing. Return True if seq is super-increasing; False otherwise.

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.
largest_less_than(N)

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:

  • N – integer; the target value to search for.

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
subset_sum(N)

Solving the subset sum problem for a super-increasing sequence.

Let S = (s_1, s_2, s_3, \dots, s_n) be a non-empty sequence of non-negative integers, and let N \in \ZZ be non-negative. 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 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:

  • N – a non-negative integer.

OUTPUT:

  • A non-empty subset of self whose elements sum to N. This subset is also a super-increasing sequence. If no such subset exists, then return the empty list.

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.

Previous topic

Numerical Optimization

Next topic

Numerical Root Finding and Optimization

This Page