时间戳

首页 > 解决方案 > 如何找到列表中增加总价值的最少项目数

python - 如何找到列表中增加总价值的最少项目数

问题描述

我有一个包含 n 个唯一值的列表。在这种情况下，变量中存储了 19 个值total。它看起来像这样：

total = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]

总的来说，这些项目以不同的方式相互关联。在此示例中，项目之间的依赖关系结构如下：

tree = [
[0],
[0, 1, 2],
[2],
[3],
[4],
[5],
[0, 1, 2, 3, 4, 5, 6, 7],
[7],
[8],
[9],
[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
[11],
[11, 12, 13, 14, 15, 16, 17, 18],
[13],
[14],
[14, 15, 16, 17, 18],
[16, 17, 18],
[17],
[17, 18]
]

我想找到最少数量的项目tree等于total. tree在此示例中，该等项中的最少项目数为total：

tree = [
[0],
[0, 1, 2],
[2],
[3],
[4],
[5],
---> [0, 1, 2, 3, 4, 5, 6, 7],
[7],
[8],
[9],
[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
[11],
---> [11, 12, 13, 14, 15, 16, 17, 18],
[13],
[14],
[14, 15, 16, 17, 18],
[16, 17, 18],
[17],
[17, 18]
]

所以它会从列表中选择第 6 和第 10 项。但是，如果tree具有不同的结构并且看起来像这样：

tree = [
[0],
[1],
[2],
[3],
[4],
[5],
[6],
[7],
[8],
[9],
[10],
[11],
[12],
[13],
[14],
[15],
[16],
[17],
[18]
]

我希望选择列表中的所有项目。

我在想的一种方法是total在求和时找到最少的项目数，以求和total。在这种情况下，总和total是 171，那么当总和等于 171 时，如何找到最少的项目tree？

标签： pythonlistnumpytreesum

解决方案

求总值

  f = 0
  for i in total:
      f += i

对你的树进行排序（从高到低）。

  def some_sorting_algoritm(tree):
      ...
      return sorted_array

简化你的分支，所以你的树数组只显示每个分支的总值（你只使用总数）：

然后从高到低循环浏览您的新列表以查看是否有任何匹配项。在这里，您将不得不提供一些逻辑。

注意：有时树的分支的数量会高于总数，因此在编写逻辑时要考虑到这一点。

推荐阅读