numpy 修剪列表,使总和接近目标值

4dbbbstv  于 2024-01-08  发布在  其他
关注(0)|答案(1)|浏览(109)

我有一个值列表,加起来是一个数字,我需要修剪它,使总和接近目标值。有没有标准的算法?我将在下面详细说明:
假设有一个名为MyClass的类,obj_list是一个包含MyClass示例的列表。每个示例都有一个名为area的属性。我可以计算总面积:
tot_area = numpy.sum([i.area for i in obj_list])
但是我需要确保总面积接近(略高于/低于)target_area值。我不能修改MyClass示例的生成方式,因为这包括从有意义的测量和一些随机化中绘制。但是,我控制有多少个(num_objs),我可以从obj_list中删除示例。我的目标是删除最小数量的示例。
我的想法是先移除面积最小的示例,然后再往上移动,但这也有一些缺点。例如,如果只移除第三大示例就足以实现目标呢?
我想知道是否有更好的方法来做到这一点。任何帮助,建议,或算法的名称是赞赏。

aiqt4smr

aiqt4smr1#

根据@JRose和an answer to a related question的评论,我发现这是一个the Knapsack Problem的例子。这个想法是比一些具有不同价值和大小的对象需要打包到一个背包中,以便在满足大小限制的情况下最大化总价值。
在我的示例中,MyClass的所有示例都具有相同的值,但具有不同的大小(称为面积)。我在SciPy文档中找到了一个工作示例,并添加了一些修改,包括目标区域的软边界。最终,这满足了我的要求。
代码如下所示:

  1. import numpy as np
  2. from scipy import optimize
  3. from scipy.optimize import milp
  4. sizes = np.array([0.003968, 0.0148, 0.022912, 0.024832, 0.02912, 0.032448,
  5. 0.034176, 0.035136, 0.035584, 0.049344, 0.057984, 0.059904,
  6. 0.063744, 0.080064, 0.085824]) # tot_area = 0.62984
  7. target_area = 0.45
  8. pct_error = 0.03 # Acceptable error as percentage of target_area.
  9. # All instances of MyClass have equal value.
  10. values = np.full_like(sizes, 1.0)
  11. # Set decision variable (x_i) to be between 0 and 1 and to be integers.
  12. # This makes them effectively Boolean, and they can be cast to bool in the end.
  13. integrality = np.full_like(values, True) # x_i must be integers within bounds.
  14. bounds = optimize.Bounds(0, 1) # x_i must be between 0 and 1.
  15. # Calculate and set the upper and lower bounds.
  16. lb = (1 - pct_error) * target_area
  17. ub = (1 + pct_error) * target_area
  18. constraints = optimize.LinearConstraint(A=sizes, lb=lb, ub=ub)
  19. optimization_result = milp(c=-values, constraints=constraints,
  20. integrality=integrality, bounds=bounds)
  21. if not optimization_result.success:
  22. raise RuntimeError('The MILP optimization procedure failed!')
  23. print(f'Total area: {sizes[optimization_result.x.astype(bool)].sum()}' )
  24. # 0.45998399999999995
  25. print(optimization_result.x)
  26. # array([0., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 0., 0.])
  27. print( sizes[optimization_result.x.astype(bool)] )
  28. # [0.0148 0.022912 0.024832 0.02912 0.032448 0.034176 0.035136 0.035584 0.049344 0.057984 0.059904 0.063744]

字符串

展开查看全部

相关问题