获取最接近1的总和的列表中的项目数量 [英] Get count of items in a list of double that sum closest to 1 wiithout going over

问题描述

我有一个包含百分比的double列表（数字从0到1）。这些数字等于制作零件所需的父材料的百分比。我想要获得所需的总材料，但我不能只是添加所有这些数字，因为它没有考虑到任何浪费。只有当您可以从剩余的剩余金额中获得下一个要求时，才能使用从1件材料中遗留下来的任何材料。请考虑以下示例：



.90

.85

.25

.65

.20



如果我加上这些数字，我得到2.85。如果我将其提高到3，那仍然不是我需要的，因为它没有考虑到所有的浪费。



我需要的是得到总和最接近1的物品的数量，而不必经过。对于第一项.90，这意味着90％将被使用，10％将被遗留。如果有另一个要求可以使用10％，那么我可以使用该项目的剩余材料。如果没有，剩余的材料就会浪费掉。由于列表中没有其他数字，因此< 10％，这10％将被浪费。这意味着.90要求将采用完整的材料。同样的事情与.85号码相同，因为没有要求< 15％所以这将需要另一整块材料。在.25项目上，使用了25％，剩下75％。列表中剩余的2个数字小于.75，因此剩余材料可用于其中之一。考虑到这一点，我可以从同一块材料中获得.25和.65的要求。在最终的.20项目中，没有其他要求，因此该项目将消耗整个部分。如果我全部添加，我将需要4件材料。



现在我正在尝试将此逻辑转换为代码。我最初认为我可以通过迭代几个不同的列表来做到这一点，但我遇到了问题。我开始删除主列表中的第一个项目，然后我创建了剩余项目的第二个列表。然后我循环浏览第二个列表，找到总和少于100％的任何数字。如果有，我然后从两个列表中删除该项目，然后继续循环。即使我在两个列表中向后循环，我也会遇到异常，我的循环计数器超出了范围。我认为当我从同一循环中的列表中删除多个项目时会发生这种情况。



我想找到一个更好的方法来做到这一点，但我已经碰到了一堵砖墙。任何想法，将不胜感激。如果重要的话，我仍在使用Dot Net 2.0。



我尝试过：

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

推荐答案

有效的木板切割算法 - Stack Overflow [ ^ ]

这篇关于获取最接近1的总和的列表中的项目数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！