Sum algorithm
-
:confused::confused::confused: I have a collection of objects (in this case, the objects are "Gauge Blocks"). Each Block in the Set (collection) has a length (i.e. 0.1009", 0.101"...). There are 81 Blocks in a Set. I need an algorithm that will determine what combination of Blocks are needed to build a stack for a given value of measurement, using the least amount of Blocks to build the stack. Also, I cannot use the same Block twice, because the Set only has one of each Block. Example: The inner width of the device being tested is 2.305". To manually build the stack from an 81 Block Set (or whatever size Set), I would normally start from the right most value of the tested dimension. In this case 5 is the right most value. I would locate a Block that has the same precision (2.305" has 3 digits of precision), so I would select a Block that has a 5 in the 3rd decimal place (i.e. 0.105" - The Blocks in each Set are NOT linear from 0.0001" to 4" in 0.0001" steps, which is why this is not as easy as I wish it was). Next I would find the next Block in the Set (2.305" - 0.105" = 2.200"), which is 0.2". That leaves me with 2", I use the 2" Block for a remainder of 0". The typical Gauge Block Set includes the following values: 0.05,0.10,0.1001,0.1002,0.1003,0.1004,0.1005,0.1006,0.1007,0.1008,0.1009,0.101,0.102, 0.103,0.104,0.105,0.106,0.107,0.108,0.109,0.110,0.111,0.112,0.113,0.114,0.115,0.116, 0.117,0.118,0.119,0.120,0.121,0.122,0.123,0.124,0.125,0.126,0.127,0.128,0.129,0.130, 0.131,0.132,0.133,0.134,0.135,0.136,0.137,0.138,0.139,0.140,0.141,0.142,0.143,0.144, 0.145,0.146,0.147,0.148,0.149,0.15,0.20,0.25,0.30,0.35,0.40,0.45,0.50,0.55,0.60,0.65, 0.70,0.75,0.80,0.85,0.90,0.95,1,2,3,4 "Some people spend an entire lifetime wondering if they made a difference. The Marines don't have that problem." ( President Ronald Reagan)
-
:confused::confused::confused: I have a collection of objects (in this case, the objects are "Gauge Blocks"). Each Block in the Set (collection) has a length (i.e. 0.1009", 0.101"...). There are 81 Blocks in a Set. I need an algorithm that will determine what combination of Blocks are needed to build a stack for a given value of measurement, using the least amount of Blocks to build the stack. Also, I cannot use the same Block twice, because the Set only has one of each Block. Example: The inner width of the device being tested is 2.305". To manually build the stack from an 81 Block Set (or whatever size Set), I would normally start from the right most value of the tested dimension. In this case 5 is the right most value. I would locate a Block that has the same precision (2.305" has 3 digits of precision), so I would select a Block that has a 5 in the 3rd decimal place (i.e. 0.105" - The Blocks in each Set are NOT linear from 0.0001" to 4" in 0.0001" steps, which is why this is not as easy as I wish it was). Next I would find the next Block in the Set (2.305" - 0.105" = 2.200"), which is 0.2". That leaves me with 2", I use the 2" Block for a remainder of 0". The typical Gauge Block Set includes the following values: 0.05,0.10,0.1001,0.1002,0.1003,0.1004,0.1005,0.1006,0.1007,0.1008,0.1009,0.101,0.102, 0.103,0.104,0.105,0.106,0.107,0.108,0.109,0.110,0.111,0.112,0.113,0.114,0.115,0.116, 0.117,0.118,0.119,0.120,0.121,0.122,0.123,0.124,0.125,0.126,0.127,0.128,0.129,0.130, 0.131,0.132,0.133,0.134,0.135,0.136,0.137,0.138,0.139,0.140,0.141,0.142,0.143,0.144, 0.145,0.146,0.147,0.148,0.149,0.15,0.20,0.25,0.30,0.35,0.40,0.45,0.50,0.55,0.60,0.65, 0.70,0.75,0.80,0.85,0.90,0.95,1,2,3,4 "Some people spend an entire lifetime wondering if they made a difference. The Marines don't have that problem." ( President Ronald Reagan)
You can use a recursive method to look for the valid combinations. Make a method that takes a specific block and the space left in the device. Let it combine the block will all combination of smaller blocks. It does that by calling itself for each smaller block that still fits in the device, to find every combination using that block and any smaller block needed. Return the least number of blocks needed to fill the remaining gap. --- b { font-weight: normal; }
-
:confused::confused::confused: I have a collection of objects (in this case, the objects are "Gauge Blocks"). Each Block in the Set (collection) has a length (i.e. 0.1009", 0.101"...). There are 81 Blocks in a Set. I need an algorithm that will determine what combination of Blocks are needed to build a stack for a given value of measurement, using the least amount of Blocks to build the stack. Also, I cannot use the same Block twice, because the Set only has one of each Block. Example: The inner width of the device being tested is 2.305". To manually build the stack from an 81 Block Set (or whatever size Set), I would normally start from the right most value of the tested dimension. In this case 5 is the right most value. I would locate a Block that has the same precision (2.305" has 3 digits of precision), so I would select a Block that has a 5 in the 3rd decimal place (i.e. 0.105" - The Blocks in each Set are NOT linear from 0.0001" to 4" in 0.0001" steps, which is why this is not as easy as I wish it was). Next I would find the next Block in the Set (2.305" - 0.105" = 2.200"), which is 0.2". That leaves me with 2", I use the 2" Block for a remainder of 0". The typical Gauge Block Set includes the following values: 0.05,0.10,0.1001,0.1002,0.1003,0.1004,0.1005,0.1006,0.1007,0.1008,0.1009,0.101,0.102, 0.103,0.104,0.105,0.106,0.107,0.108,0.109,0.110,0.111,0.112,0.113,0.114,0.115,0.116, 0.117,0.118,0.119,0.120,0.121,0.122,0.123,0.124,0.125,0.126,0.127,0.128,0.129,0.130, 0.131,0.132,0.133,0.134,0.135,0.136,0.137,0.138,0.139,0.140,0.141,0.142,0.143,0.144, 0.145,0.146,0.147,0.148,0.149,0.15,0.20,0.25,0.30,0.35,0.40,0.45,0.50,0.55,0.60,0.65, 0.70,0.75,0.80,0.85,0.90,0.95,1,2,3,4 "Some people spend an entire lifetime wondering if they made a difference. The Marines don't have that problem." ( President Ronald Reagan)
-
If this is homework (which I'm sure it is), you should probably try it first and post questions if you get stuck. If somebody here does it for you, you lean nothing.
I work for Lockheed Martin as a Metrologist, this is for personal and work related intrests. There would be no reason for this message board to exist if it wasn't here to help others out. I give my 110% and rarely ask for 1% in return, all I need is a faster way to build a Gauge Block stack. Thanks for the post. "Some people spend an entire lifetime wondering if they made a difference. The Marines don't have that problem." ( President Ronald Reagan) -- modified at 16:02 Wednesday 5th April, 2006
-
You can use a recursive method to look for the valid combinations. Make a method that takes a specific block and the space left in the device. Let it combine the block will all combination of smaller blocks. It does that by calling itself for each smaller block that still fits in the device, to find every combination using that block and any smaller block needed. Return the least number of blocks needed to fill the remaining gap. --- b { font-weight: normal; }
Thanks, that's a big help. I'll post some code after I compile it. Thanks again, Scott Page "Some people spend an entire lifetime wondering if they made a difference. The Marines don't have that problem." ( President Ronald Reagan)
-
If this is homework (which I'm sure it is), you should probably try it first and post questions if you get stuck. If somebody here does it for you, you lean nothing.
-
:confused::confused::confused: I have a collection of objects (in this case, the objects are "Gauge Blocks"). Each Block in the Set (collection) has a length (i.e. 0.1009", 0.101"...). There are 81 Blocks in a Set. I need an algorithm that will determine what combination of Blocks are needed to build a stack for a given value of measurement, using the least amount of Blocks to build the stack. Also, I cannot use the same Block twice, because the Set only has one of each Block. Example: The inner width of the device being tested is 2.305". To manually build the stack from an 81 Block Set (or whatever size Set), I would normally start from the right most value of the tested dimension. In this case 5 is the right most value. I would locate a Block that has the same precision (2.305" has 3 digits of precision), so I would select a Block that has a 5 in the 3rd decimal place (i.e. 0.105" - The Blocks in each Set are NOT linear from 0.0001" to 4" in 0.0001" steps, which is why this is not as easy as I wish it was). Next I would find the next Block in the Set (2.305" - 0.105" = 2.200"), which is 0.2". That leaves me with 2", I use the 2" Block for a remainder of 0". The typical Gauge Block Set includes the following values: 0.05,0.10,0.1001,0.1002,0.1003,0.1004,0.1005,0.1006,0.1007,0.1008,0.1009,0.101,0.102, 0.103,0.104,0.105,0.106,0.107,0.108,0.109,0.110,0.111,0.112,0.113,0.114,0.115,0.116, 0.117,0.118,0.119,0.120,0.121,0.122,0.123,0.124,0.125,0.126,0.127,0.128,0.129,0.130, 0.131,0.132,0.133,0.134,0.135,0.136,0.137,0.138,0.139,0.140,0.141,0.142,0.143,0.144, 0.145,0.146,0.147,0.148,0.149,0.15,0.20,0.25,0.30,0.35,0.40,0.45,0.50,0.55,0.60,0.65, 0.70,0.75,0.80,0.85,0.90,0.95,1,2,3,4 "Some people spend an entire lifetime wondering if they made a difference. The Marines don't have that problem." ( President Ronald Reagan)
This problem is usually framed in the guise of how to provide the least number of coins in change. See this Google search[^] I had a thought that the 'greedy algorithm' would be a good choice but it did not find a solution to 2.305. (The greedy algorithm always takes the highest possible amount from the required sum, remainder and so on - almost opposite to the algorithm you proposed.) Maybe a least-spanning tree algorithm is the way to go? I also note that with the sample set you provided, you cannot make up a stack of 0.06". Is this correct?
...Steve1. quod erat demonstrandum 2. "Give a man a fish and you've fed him for a day. Teach him how to fish and you've fed him for life." I read that somewhere once :-) -
This problem is usually framed in the guise of how to provide the least number of coins in change. See this Google search[^] I had a thought that the 'greedy algorithm' would be a good choice but it did not find a solution to 2.305. (The greedy algorithm always takes the highest possible amount from the required sum, remainder and so on - almost opposite to the algorithm you proposed.) Maybe a least-spanning tree algorithm is the way to go? I also note that with the sample set you provided, you cannot make up a stack of 0.06". Is this correct?
...Steve1. quod erat demonstrandum 2. "Give a man a fish and you've fed him for a day. Teach him how to fish and you've fed him for life." I read that somewhere once :-)Thanks for the post, I am getting closer to my goal, but still no cigar (I mean stack). Below is the function I'm using to build the stack. In answer to you question about the 0.06" height, Block Sets are manufactured to cover nearly all possible heights seen in the manufacturing and Metrology worlds. If a value does not exist, there other methods used to measure those dimensions. This function gets me as close as 2.203". I tested the function using 2.203" (correct result), 2.205" (still got 2.203"), 2.305" (still got 2.203"). The returned stack has the 0.101", 0.102" and 2" blocks used, so obviously, since I can't use the 0.102" block, I can't cover the last 0.102" of the height. The Code:
'This function exists within a custom collection Public Function GetStack(ByVal height As Decimal) As GageBlockCollection Me.ClearUsedBlocks() Dim Stack As New GageBlockCollection If Me.HasEqualGageBlock(height) Then Stack.Add(Me.GetEqualGageBlock(height)) Return Stack Else Dim PossibleBlocks As New GageBlockCollection If height >= 1 Then 'Height is greater than 1", so find the block that makes eliminates the inch part For Each Block As GageBlock In Me If height - Block.Height > 0 AndAlso height - block.Height < 1 Then Block.IsUsed = True PossibleBlocks.Add(block) height -= Block.Height End If Next End If 'Find all blocks that are less than the remaining Height (the inch part has been removed) For Each Block As GageBlock In Me If Not Block.IsUsed AndAlso Block.Height <= height AndAlso Block.Height.ToString.Length = height.ToString.Length Then If Block.Height = height Then Stack.Add(Block) Block.IsUsed = True For Each B As GageBlock In PossibleBlocks Stack.Add(B) Next Return Stack Else Stack.Add(Block) Block.IsUsed = True height -= Block.Height End If End If Next If Not height = 0 Then For Each Block As GageBlock In PossibleBlocks -
:confused::confused::confused: I have a collection of objects (in this case, the objects are "Gauge Blocks"). Each Block in the Set (collection) has a length (i.e. 0.1009", 0.101"...). There are 81 Blocks in a Set. I need an algorithm that will determine what combination of Blocks are needed to build a stack for a given value of measurement, using the least amount of Blocks to build the stack. Also, I cannot use the same Block twice, because the Set only has one of each Block. Example: The inner width of the device being tested is 2.305". To manually build the stack from an 81 Block Set (or whatever size Set), I would normally start from the right most value of the tested dimension. In this case 5 is the right most value. I would locate a Block that has the same precision (2.305" has 3 digits of precision), so I would select a Block that has a 5 in the 3rd decimal place (i.e. 0.105" - The Blocks in each Set are NOT linear from 0.0001" to 4" in 0.0001" steps, which is why this is not as easy as I wish it was). Next I would find the next Block in the Set (2.305" - 0.105" = 2.200"), which is 0.2". That leaves me with 2", I use the 2" Block for a remainder of 0". The typical Gauge Block Set includes the following values: 0.05,0.10,0.1001,0.1002,0.1003,0.1004,0.1005,0.1006,0.1007,0.1008,0.1009,0.101,0.102, 0.103,0.104,0.105,0.106,0.107,0.108,0.109,0.110,0.111,0.112,0.113,0.114,0.115,0.116, 0.117,0.118,0.119,0.120,0.121,0.122,0.123,0.124,0.125,0.126,0.127,0.128,0.129,0.130, 0.131,0.132,0.133,0.134,0.135,0.136,0.137,0.138,0.139,0.140,0.141,0.142,0.143,0.144, 0.145,0.146,0.147,0.148,0.149,0.15,0.20,0.25,0.30,0.35,0.40,0.45,0.50,0.55,0.60,0.65, 0.70,0.75,0.80,0.85,0.90,0.95,1,2,3,4 "Some people spend an entire lifetime wondering if they made a difference. The Marines don't have that problem." ( President Ronald Reagan)
Thanks to All for your help, Here is the code that has worked on several target height values passed. (Not quite sure how this "code" thing works yet)
'This function exists within a custom collection Public Function GetStack(ByVal height As Decimal) As GageBlockCollection Me.ClearUsedBlocks() Dim Stack As New GageBlockCollection If Me.HasEqualGageBlock(height) Then Stack.Add(Me.GetEqualGageBlock(height)) Return Stack Else Dim PossibleBlocks As New GageBlockCollection If height >= 1 Then 'Height is greater than 1", so find the block that makes eliminates the inch part For Each Block As GageBlock In Me If height - Block.Height > 0 AndAlso height - block.Height < 1 Then Block.IsUsed = True PossibleBlocks.Add(block) height -= Block.Height End If Next End If 'Find all Blocks that are smaller than height For Each Block As GageBlock In Me If Block.Height < height AndAlso Not Block.IsUsed Then PossibleBlocks.Add(block) End If Next 'Find combinations of blocks that are less that height Dim Done As Boolean = False For Each Block1 As GageBlock In PossibleBlocks For Each Block2 As GageBlock In PossibleBlocks If height - (Block1.Height + Block2.Height) = 0 Then Block1.IsUsed = True Block2.IsUsed = True Stack.Add(Block1) Stack.Add(Block2) Done = True Exit For End If Next If Done Then Exit For End If Next For Each Block As GageBlock In PossibleBlocks If Block.IsUsed Then Stack.Add(block) End If Next Return Stack End If End FunctionThanks again, Scott Page "Some people spend an entire lifetime wondering if they made a difference. The Marines don't have that problem." ( President Ronald Reagan) -
Thanks for the post, I am getting closer to my goal, but still no cigar (I mean stack). Below is the function I'm using to build the stack. In answer to you question about the 0.06" height, Block Sets are manufactured to cover nearly all possible heights seen in the manufacturing and Metrology worlds. If a value does not exist, there other methods used to measure those dimensions. This function gets me as close as 2.203". I tested the function using 2.203" (correct result), 2.205" (still got 2.203"), 2.305" (still got 2.203"). The returned stack has the 0.101", 0.102" and 2" blocks used, so obviously, since I can't use the 0.102" block, I can't cover the last 0.102" of the height. The Code:
'This function exists within a custom collection Public Function GetStack(ByVal height As Decimal) As GageBlockCollection Me.ClearUsedBlocks() Dim Stack As New GageBlockCollection If Me.HasEqualGageBlock(height) Then Stack.Add(Me.GetEqualGageBlock(height)) Return Stack Else Dim PossibleBlocks As New GageBlockCollection If height >= 1 Then 'Height is greater than 1", so find the block that makes eliminates the inch part For Each Block As GageBlock In Me If height - Block.Height > 0 AndAlso height - block.Height < 1 Then Block.IsUsed = True PossibleBlocks.Add(block) height -= Block.Height End If Next End If 'Find all blocks that are less than the remaining Height (the inch part has been removed) For Each Block As GageBlock In Me If Not Block.IsUsed AndAlso Block.Height <= height AndAlso Block.Height.ToString.Length = height.ToString.Length Then If Block.Height = height Then Stack.Add(Block) Block.IsUsed = True For Each B As GageBlock In PossibleBlocks Stack.Add(B) Next Return Stack Else Stack.Add(Block) Block.IsUsed = True height -= Block.Height End If End If Next If Not height = 0 Then For Each Block As GageBlock In PossibleBlocks