我有一个值列表,加起来是一个数字,我需要修剪它,使总和接近目标值。有没有标准的算法?我将在下面详细说明:
假设有一个名为MyClass
的类,obj_list
是一个包含MyClass
示例的列表。每个示例都有一个名为area
的属性。我可以计算总面积:tot_area = numpy.sum([i.area for i in obj_list])
个
但是我需要确保总面积接近(略高于/低于)target_area
值。我不能修改MyClass
示例的生成方式,因为这包括从有意义的测量和一些随机化中绘制。但是,我控制有多少个(num_objs
),我可以从obj_list
中删除示例。我的目标是删除最小数量的示例。
我的想法是先移除面积最小的示例,然后再往上移动,但这也有一些缺点。例如,如果只移除第三大示例就足以实现目标呢?
我想知道是否有更好的方法来做到这一点。任何帮助,建议,或算法的名称是赞赏。
1条答案
按热度按时间aiqt4smr1#
根据@JRose和an answer to a related question的评论,我发现这是一个the Knapsack Problem的例子。这个想法是比一些具有不同价值和大小的对象需要打包到一个背包中,以便在满足大小限制的情况下最大化总价值。
在我的示例中,
MyClass
的所有示例都具有相同的值,但具有不同的大小(称为面积)。我在SciPy文档中找到了一个工作示例,并添加了一些修改,包括目标区域的软边界。最终,这满足了我的要求。代码如下所示:
字符串