Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Iterator : Iterator/FillRucksack

Iterator

  

FillRucksack

  

generate feasible ways to fill a rucksack

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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.

Examples

withIterator:

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

W1,2,2,4,8:

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

MFillRucksackW,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.

forfinMdolenlengthM;printf%d = [%{c,}d]\n,addWfk,k=1..len,f1..lenenddo:

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.

seqaddWfk,k=1..lengthM=f1..lengthM,m=M

0=,1=1,2=2,3=21,2=3,3=31,4=32,5=321,4=4,5=41,6=42,7=421,6=43,7=431,8=432,9=4321,8=5,9=51,10=52,11=521,10=53,11=531,12=532,13=5321,12=54,13=541,14=542,15=5421,14=543,15=5431

(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.

• 

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

See Also

Iterator