计算合并子集以获得原始s的成本

2024-03-28 17:22:28 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一份清单

[1,2,3]

我有上面列表中的一些子集的字典,例如有一个特殊的费用

{
(1) : 5.0,
(2) : 3.0,
(3) : 2.5, 
(1,3) : 6.0,
(2,3) : 5.0,
}

我得想办法以最低的成本得到上面的清单。例如,我可以通过combining (1),(2),(3) with a cost of 10.5,combining (1,3) and (2) with a cost of 9.0combining (1) and (2,3) with a cost of 10.0得到[1,2,3]。用我的第二个选择,我将能够得到最低的成本。你知道吗

我能想到的解决方案是对上面的列表[1,2,3]进行一组划分,如果字典中存在特定的子集组合,则进行匹配。但是这个解决方案并不是最优的,因为生成列表的集合分区会带来巨大的成本。你知道吗

see this link for ref.用于集合划分算法


Tags: andof列表字典with解决方案this子集
1条回答
网友
1楼 · 发布于 2024-03-28 17:22:28

尝试:

  • 从dict中丢弃任何一组成本大于等于每个项目成本的两个项目。你知道吗
  • 从dict中丢弃任何一组三个项目,其成本大于等于某组大小大于等于3的组合的成本。你知道吗
  • 。。。你知道吗

贪婪算法位:

  • 随机选择一个最大的dicts集
  • 重复地将两个
    1. 覆盖目标集的大部分剩余项
    2. 然后,成本最低。你知道吗

上面的内容应该比纯粹的随机选择更好。你知道吗

相关问题 更多 >