compile = truefalse

True means compile the iterator. The default is true.

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.

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

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

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

$$\begin{gathered} \mathbf{for}f\mathbf{in}M\mathbf{do} \\ \mathrm{len}≔\mathrm{length}\left(M\right); \\ \mathrm{printf}\left(''\%d\; =\; [\%\{c,\}d]\backslash n''\,\mathrm{add}\left(W\left[f\left[k\right]\right]\,k=1..\mathrm{len}\right)\,f\left[1..\mathrm{len}\right]\right) \\ \mathbf{end}\mathbf{do}\: \end{gathered}$$

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]

$\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]$

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.

The Iterator[FillRucksack] command was introduced in Maple 2016.

For more information on Maple 2016 changes, see Updates in Maple 2016.