Get count of items in a list of double that sum closest to 1 wiithout going over

See more:

VB

collections

I have a list of double that contains percentages (numbers from 0 to 1). These numbers equate to the percentage of a parent piece of material required to make part. I am trying to get the total material required but I can’t just add all these numbers up because it doesn’t account for any waste. Any material left over from 1 piece of material can only be used when you can get the entire next requirement from that leftover amount. Consider the following example:

.90
.85
.25
.65
.20

If I add up these numbers, I get 2.85. If I would round that up to 3, that is still not what I need because it doesn’t account for all the waste.

What I need is to get the count of the items that sum up closest to 1 without going over. For the first item .90, that means 90% will be used and 10% will be left over. If there is another requirement that can use that 10%, then I can use the remaining material for that item. If not, the remaining material goes to waste. Since there is no other number in the list that is < 10%, that 10% will be wasted. This means the .90 requirement will take a full piece of material. Same thing goes with the .85 number because there is no requirement < 15% so this will require another whole piece of material. On the .25 item, 25% is used and 75% is left over. There are 2 numbers remaining on the list that are smaller than the .75 so this left over material can be used for one of those. With this in mind, I can get the .25 and the .65 requirement out of the same piece of material. On the final .20 item, there is no other requirements so that item is going to consume the entire piece. If I add this all up, I will need 4 pieces of material.

Now I am trying to convert this logic into code. I initially thought I could do this by iterating though a couple of different lists but I am having issues. I started out by removing the first item off the main list and then I created a 2nd list of the remaining items. I then loop through the 2nd list to find any numbers that sum up less 100%. If there are, I then remove the item from both lists and then continue looping. Even though I am looping backwards in both lists, I am getting exceptions where my loop counters are going out of range. I think this happening when I remove multiple items from a list in the same loop.

I am trying to figure out a better way to do this but I have hit a brick wall. Any ideas would be appreciated. If it matters, I am still using Dot Net 2.0.

What I have tried:

Private Sub BtnTest_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles BtnTest.Click

       Dim PercentList As New List(Of Double)
       Dim RoundUpUsage As Integer = 0

       PercentList.Add(0.9)
       PercentList.Add(0.85)
       PercentList.Add(0.25)
       PercentList.Add(0.65)
       PercentList.Add(0.2)

       RoundUpUsage = FindRoundUpCutterUsageCount(PercentList)

       MsgBox("Round Up Usage = " & RoundUpUsage)


   End Sub

Private Function FindRoundUpCutterUsageCount(ByVal PercentList As List(Of Double)) As Integer

        'This functions finds the cutter usage count based on totaling all 
        'the tool life %'s in the list
        'It won't let the total of any 2 or more list item go over 100%


        Dim CountResult As Integer = 0
        Dim PercX As Double = 0                             'Percentage from the X loop
        Dim PercY As Double = 0                             'Percentage from the Y loop
        Dim PercTotal As Double = 0                         'Total % (not to go over 100%)


        'Loop through the incoming list backwards
        For X As Integer = PercentList.Count - 1 To 0 Step -1

            Debug.WriteLine("X = " & X & " PercentListCount = " & PercentList.Count)
            'Get the 1st item from the list
            PercX = PercentList(X)
            PercTotal = PercX

            Debug.WriteLine("PercX(" & X & ") = " & PercX)

            'Remove the first item from the list
            Debug.WriteLine("Removing " & PercX & " from PercentList")
            PercentList.RemoveAt(X)

            'Copy the list to an unassociative variable
            Dim ListCopy As List(Of Double) = CopyList(PercentList)

            'Loop through the copied list
            For Y As Integer = ListCopy.Count - 1 To 0 Step -1

                Debug.WriteLine("Y = " & Y & " ListCopyCount = " & ListCopy.Count)

                'Find the next %
                PercY = ListCopy(Y)

                Debug.WriteLine("PercY(" & Y & ") = " & PercY)

                'See if the running total will be exceeded
                If PercY + PercTotal > 1 Then
                    'Try the next item
                    Debug.WriteLine(PercY & " + " & PercTotal & " > 1 - skipping to next item")
                    Continue For
                Else
                    'Running Total NOT exceeded
                    'Update the total
                    Debug.WriteLine(PercY & " + " & PercTotal & " = " & PercY + PercTotal)
                    PercTotal += PercY

                    'Remove this item from the both lists then
                    'continue to see if more items can be summed up
                    Debug.WriteLine("Removing " & X & " from PercentList")
                    PercentList.Remove(PercY)
                    Debug.WriteLine("Removing item " & Y & " from ListCopy")
                    ListCopy.RemoveAt(Y)

                End If

            Next

            'Reached the end of the ListCopy loop
            CountResult += 1
            Debug.WriteLine("Running Count Total = " & CountResult)

        Next

        Return CountResult

    End Function

Private Function CopyList(ByVal OriginalList As List(Of Double)) As List(Of Double)

        'Copies the list to a new list
        Dim NewList As New List(Of Double)

        For Each num As Double In OriginalList
            NewList.Add(num)
        Next

        Return NewList

    End Function