Fill Rucksack - Maple Help

Iterator

 FillRucksack
 generate feasible ways to fill a rucksack

 Calling Sequence FillRucksack(W, C, opts)

Parameters

 W - list(nonnegint); sorted sizes of items C - nonnegative; capacity of rucksack opts - (optional) equation(s) of the form option = value; specify options for the FillRucksack command

Options

 • compile = truefalse
 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.
 • This iterator object has the common iterator methods.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Assume we have items with sizes 1, 2, 2, 4, and 8.

 > $W≔\left[1,2,2,4,8\right]:$

Construct the iterator, assuming the rucksack has capacity of 15.

 > $M≔\mathrm{FillRucksack}\left(W,15\right):$

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.

 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}f\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}M\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{len}≔\mathrm{length}\left(M\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%d = \left[%\left\{c,\right\}d\right]\n",\mathrm{add}\left(W\left[f\left[k\right]\right],k=1..\mathrm{len}\right),f\left[1..\mathrm{len}\right]\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 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.

 > $\mathrm{seq}\left(\mathrm{add}\left(W\left[f\left[k\right]\right],k=1..\mathrm{length}\left(M\right)\right)=f\left[1..\mathrm{length}\left(M\right)\right],m=M\right)$
 ${0}{=}\left[\begin{array}{}\end{array}\right]{,}{1}{=}\left[\begin{array}{c}{1}\end{array}\right]{,}{2}{=}\left[\begin{array}{c}{2}\end{array}\right]{,}{3}{=}\left[\begin{array}{cc}{2}& {1}\end{array}\right]{,}{2}{=}\left[\begin{array}{c}{3}\end{array}\right]{,}{3}{=}\left[\begin{array}{cc}{3}& {1}\end{array}\right]{,}{4}{=}\left[\begin{array}{cc}{3}& {2}\end{array}\right]{,}{5}{=}\left[\begin{array}{ccc}{3}& {2}& {1}\end{array}\right]{,}{4}{=}\left[\begin{array}{c}{4}\end{array}\right]{,}{5}{=}\left[\begin{array}{cc}{4}& {1}\end{array}\right]{,}{6}{=}\left[\begin{array}{cc}{4}& {2}\end{array}\right]{,}{7}{=}\left[\begin{array}{ccc}{4}& {2}& {1}\end{array}\right]{,}{6}{=}\left[\begin{array}{cc}{4}& {3}\end{array}\right]{,}{7}{=}\left[\begin{array}{ccc}{4}& {3}& {1}\end{array}\right]{,}{8}{=}\left[\begin{array}{ccc}{4}& {3}& {2}\end{array}\right]{,}{9}{=}\left[\begin{array}{cccc}{4}& {3}& {2}& {1}\end{array}\right]{,}{8}{=}\left[\begin{array}{c}{5}\end{array}\right]{,}{9}{=}\left[\begin{array}{cc}{5}& {1}\end{array}\right]{,}{10}{=}\left[\begin{array}{cc}{5}& {2}\end{array}\right]{,}{11}{=}\left[\begin{array}{ccc}{5}& {2}& {1}\end{array}\right]{,}{10}{=}\left[\begin{array}{cc}{5}& {3}\end{array}\right]{,}{11}{=}\left[\begin{array}{ccc}{5}& {3}& {1}\end{array}\right]{,}{12}{=}\left[\begin{array}{ccc}{5}& {3}& {2}\end{array}\right]{,}{13}{=}\left[\begin{array}{cccc}{5}& {3}& {2}& {1}\end{array}\right]{,}{12}{=}\left[\begin{array}{cc}{5}& {4}\end{array}\right]{,}{13}{=}\left[\begin{array}{ccc}{5}& {4}& {1}\end{array}\right]{,}{14}{=}\left[\begin{array}{ccc}{5}& {4}& {2}\end{array}\right]{,}{15}{=}\left[\begin{array}{cccc}{5}& {4}& {2}& {1}\end{array}\right]{,}{14}{=}\left[\begin{array}{ccc}{5}& {4}& {3}\end{array}\right]{,}{15}{=}\left[\begin{array}{cccc}{5}& {4}& {3}& {1}\end{array}\right]$ (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.