轻松的编程学习
首页
题库
学习路径
在线商城
能力地图
下载应用
登录 / 注册
菜单
⚠️ 最优要试多少个子集
👁️ 0 人浏览
💬 0 人评论
❤️ 添加收藏
暴力求最优要一个个试子集。数一数它试了多少个、贪心只看了多少条边，再算出七个点一共有多少个子集。
提交你的答案
请登录后提交答案。
去登录
← 🔴 两张图的近似比，都没超过 2
把 A 归到 B，是在做什么 →
更多题目
让程序说出"你好"
让程序欢迎你
哪个命令能显示内容
哪里是指令，哪里是结果
让程序说出你的名字
这个程序会显示什么
代码编辑器
语言：
python3
c11
cpp17
Ctrl
+
Enter
运行
👩🏫 AI
▶ 运行代码
重置代码
打印代码
from itertools import combinations import math E = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4), (4, 5), (5, 6), (4, 6)] V = [0, 1, 2, 3, 4, 5, 6] def opt_vc_steps(edges, vs): """暴力找最优，顺便数一数试了多少个子集""" steps = 0 for k in range(len(vs) + 1): for c in combinations(vs, k): steps += 1 s = set(c) if all(a in s or b in s for a, b in edges): return len(s), steps return len(vs), steps def greedy_steps(edges): """贪心，顺便数一数看了多少条边""" cover, used, steps = [], set(), 0 for a, b in edges: steps += 1 if a not in used and b not in used: cover += [a, b] used |= {a, b} return len(cover), steps # TODO: 暴力试了多少个子集、贪心看了多少条边 brute_steps, fast_steps = -1, -1 # TODO: 七个点的全部子集一共有多少个（2 的 7 次方） all_subsets = -1 print(str(brute_steps) + "/" + str(fast_steps) + "/" + str(all_subsets))
本次输入：
输出：
👩🏫
AI
请登录后使用 AI 老师
×
登录后可获得解题思路、提示与错误分析。
去登录
关闭
🎉
恭喜你，回答正确！
系统判定：正确
我知道了
💬 题目评论
提交
全部评论
全部评论