问题如下:如果有一个集合S = {x1, ..., x_n}
和一个函数f
:set->;数字,它以一个集合作为输入并返回一个数字作为输出,什么是最好的联盟结构(联盟结构是S
的子集集合。也就是说,找到子集,使得S
中每个子集s_i
的f(s_i)
之和是最大的)。联盟中的集合不应重叠,它们的并集应为S
。
模板如下所示:
def optimal_coalition(coalitions):
"""
:param coalitions: a dictionary of the form {coalition: value}, where coalition is a set, and value is a number
:return:
"""
optimal_coalition({set(1): 30, set(2): 40, set(1, 2): 71}) # Should return set(set(1, 2))
我翻译了伪代码。毫无疑问,你可以做得更好。我正在仔细地挖掘,以显示这种联系
我确实修复了一个bug(
Val(C') + Val(C \ C') > v(C)
应该是Val(C') + Val(C \ C') > Val(C)
,否则我们可能会用一个比所有C
更好的分区覆盖最好的分区)和两个打字错误(C / C'
应该是C \ C'
;CS*
是一个集合,而不是一个树)相关问题 更多 >
编程相关推荐