巨蟒。贪婪算法，2用于循环遍历列表

Question

我正在尝试写一个贪婪的算法，其中我有一个限制，我可以在一个盒子中容纳多少项目，我必须在进入下一个之前，在一个盒子中容纳尽可能多的项目(即最大化每个盒子的重量)。

我一直在尝试通过创建两个完全相同的列表来解决这个问题，比如a_list和b_list。

a_list = [9, 8, 6, 4, 3, 2, 2, 2]
b_list = [9, 8, 6, 4, 3, 2, 2, 2]

在这里，每个框的约束是10，因此，例如，我只能在移动到下一个框之前将第一项(9)放入一个框中。下面的框应该包含8+ 2。

每个框都是主列表中的一个列表(即

list_ = [[9], [8,2],[6,4].....]

我只能移动到下一个盒子，一旦当前的一个不能有更多的项目在它里面。

当我尝试遍历这两个列表时，我不知道如何删除项以避免它们在list_中多次出现。

我很接近了，但我有几个项目出现了两次，而其中一个根本没有出现。

同样的情况是，尽管我按降序对列表进行排序，但并不是所有的框都是最佳的，其中一个框中只有一个值为“2”的项。我知道这与循环有关，但我不明白为什么它不按降序遍历项目。

limit = 10
list_ = [[]]

for i in a_list:
   for j in b_list:            

       if sum(l[-1]) + i + j <= limit:

           l[-1].append(i)
           l[-1].append(j)
           b_list.remove(j)

       elif sum(l[-1]) + j <= limit:
           l[-1].append(j)
           b_list.remove(j)

       else:
           l.append([])

Answer 1

我认为您使用a_list和b_list的唯一原因是，您假设需要为每个框挑选两个项目，但事实并非如此。

我认为你应该使用单个列表，并使用基于列表索引的方法来跟踪添加了哪些项目。

您还会遇到删除的问题，因此请尝试设置添加到-1的项，并在每次遍历后将其过滤掉，以避免在循环时与删除混淆。

我拒绝在这里分享解决方案代码，但是如果你需要的话，可以ping我。

Answer 2

在遍历列表时更改列表始终是一个挑战。这里有一个使用while循环的解决方案，我通常不赞成它，但它是一个足够简单的算法，它在这里应该没有问题。

while循环检查初始列表中是否还有元素。然后，它弹出(删除并保存)列表的第一个元素，并遍历列表的其余部分，查找满足求和条件小于约束的其他元素。如果找到一个元素，则将其附加到子列表中，并记录其索引。在for循环的末尾，子列表被附加到输出列表，然后记录的索引以相反的顺序被移除。

a_list = [9, 8, 6, 4, 3, 2, 2, 2]
constraint = 10

out = []
while a_list:
    # grab first element of a_list and reset the list of  
    # to pop from a_list to pop from a_list
    sub_out = [a_list.pop(0)]
    pop_list = []

    for i,a in enumerate(a_list):
        if a+sum(sub_out) <= constraint:
            sub_out.append(a)
            pop_list.append(i)

    # append the sub_list to the output list
    out.append(sub_out)
    # remove each item in the pop_list in the reverse order 
    for i in reversed(pop_list):
        a_list.pop(i)

#output:
>>> out
[[9], [8, 2], [6, 4], [3, 2, 2]]