Line: 1 to 1 | ||||||||
---|---|---|---|---|---|---|---|---|

## Depth-First Search for Enumeration | ||||||||

Line: 73 to 73 | ||||||||

let number[current] := number[current] + 1; } else { # Too many cut, backtrack up the tree | ||||||||

Deleted: | ||||||||

< < | print "Problem"; display current, number; | |||||||

let number[current] := 0; if current = first(ROLLS) then let stillSearching := 0; | ||||||||

Line: 82 to 80 | ||||||||

let current := prev(current, ROLLS); let number[current] := number[current] + 1; } | ||||||||

Deleted: | ||||||||

< < | display current, number; | |||||||

} } while stillSearching; | ||||||||

Line: 94 to 91 | ||||||||

We start at the root node and search on the first possibility at level 1 (the 5cm rolls):
| ||||||||

Changed: | ||||||||

< < | let current := first(ITEMS); | |||||||

> > | # Start with the first product and no ROLLS being cut let current := first(ROLLS); | |||||||

let number[current] := 0; let stillSearching := 1; | ||||||||

Line: 103 to 101 | ||||||||

- If we are not at the lowest level (the 9cm rolls) and we have a valid possibility for this node then
*dive*to the next level:
| ||||||||

Changed: | ||||||||

< < | if ( current <> last(ITEMS) ) and | |||||||

> > | if ( current <> last(ROLLS) ) and | |||||||

( number[current] <= MaxPossible[current] ) then { | ||||||||

Changed: | ||||||||

< < | let current := next(current, ITEMS); | |||||||

> > | let current := next(current, ROLLS); | |||||||

let number[current] := 0; } | ||||||||

Changed: | ||||||||

< < | ||||||||

> > | current = last(ROLLS)) and have a valid possibility, then evaluate the pattern we have found and move to the next possibility: | |||||||

else if number[current] <= MaxPossible[current] then { | ||||||||

Changed: | ||||||||

< < | # current = last(ITEMS), cutting pattern found | |||||||

> > | # current = last(ROLLS), cutting pattern found | |||||||

# Save the pattern | ||||||||

Changed: | ||||||||

< < | if ( sum {i in ITEMS} number[i] * Length[i] <= TotalLength) and ( TotalLength - sum {i in ITEMS} number[i] * Length[i] < MinLength) then { | |||||||

> > | if ( sum {i in ROLLS} number[i] * Length[i] <= TotalLength) and ( TotalLength - sum {i in ROLLS} number[i] * Length[i] < MinLength) then { | |||||||

let newPattern := card(PATTERNS) + 1; let PATTERNS := PATTERNS union {newPattern}; | ||||||||

Changed: | ||||||||

< < | let {i in ITEMS} PatternYield[newPattern, i] := number[i]; } | |||||||

> > | let YIELDS[newPattern] := {i in ROLLS : number[i] > 0}; let {i in YIELDS[newPattern]} PatternYield[newPattern, i] := number[i]; | |||||||

} # Increase the number cut let number[current] := number[current] + 1; | ||||||||

Line: 129 to 127 | ||||||||

else { # Too many cut, backtrack up the tree let number[current] := 0; | ||||||||

Changed: | ||||||||

< < | if current = first(ITEMS) then | |||||||

> > | if current = first(ROLLS) then | |||||||

let stillSearching := 0; else { | ||||||||

Changed: | ||||||||

< < | let current := prev(current, ITEMS); | |||||||

> > | let current := prev(current, ROLLS); | |||||||

let number[current] := number[current] + 1; } } |

View topic | History: r6 < r5 < r4 < r3 | More topic actions...

Copyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback