|
Calling Sequence
|
|
FillRucksack(W, C, opts)
|
|
Parameters
|
|
W
|
-
|
list(nonnegint); sorted sizes of items
|
C
|
-
|
nonnegint; capacity of rucksack
|
opts
|
-
|
(optional) equation(s) of the form option = value; specify options for the FillRucksack command
|
|
|
|
|
Options
|
|
|
True means compile the iterator. The default is true.
|
|
|
Description
|
|
•
|
The FillRucksack command returns an iterator that generates all feasible ways to fill a rucksack with a list of items.
|
•
|
The W parameter is a list of nonnegative numbers corresponding to the size of each item. The list is assumed to be sorted from smallest to largest.
|
•
|
The C parameter is a nonnegative number that specifies the capacity of the rucksack.
|
•
|
For each iteration, the number of valid indices in the Array returned by the getNext method is given by the length method of the iterator object.
|
|
|
Examples
|
|
Assume we have items with sizes 1, 2, 2, 4, and 8.
>
|
|
Construct the iterator, assuming the rucksack has capacity of 15.
>
|
|
Print the list of all ways to pack the rucksack. The lhs of each equation is the sum of the sizes; the rhs is a list of indices of the items. The length method returns the number of elements in the rucksack.
>
|
|
0 = []
1 = [1]
2 = [2]
3 = [2,1]
2 = [3]
3 = [3,1]
4 = [3,2]
5 = [3,2,1]
4 = [4]
5 = [4,1]
6 = [4,2]
7 = [4,2,1]
6 = [4,3]
7 = [4,3,1]
8 = [4,3,2]
9 = [4,3,2,1]
8 = [5]
9 = [5,1]
10 = [5,2]
11 = [5,2,1]
10 = [5,3]
11 = [5,3,1]
12 = [5,3,2]
13 = [5,3,2,1]
12 = [5,4]
13 = [5,4,1]
14 = [5,4,2]
15 = [5,4,2,1]
14 = [5,4,3]
15 = [5,4,3,1]
| |
Here we do the same thing, but with a sequence.
>
|
|
| (1) |
|
|
References
|
|
|
Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions. p. 7, sec. 7.2.1.3, generating all combinations, algorithm F, filling a rucksack.
|
|
|
Compatibility
|
|
•
|
The Iterator[FillRucksack] command was introduced in Maple 2016.
|
|
|
|
|