⚠️ 换一张图,比值正好顶到 2
换一张图:三条互不相连的边 [(0, 1), (2, 3), (4, 5)]。贪心和最优各要几个点? from itertools import combinations E2 = [(0, 1), (2, 3), (4, 5)] V2
自己写:2-近似的顶点覆盖
补全贪心:挨条边看,两头都没被盖住就把两头一起收下。
🔴 两张图的近似比,都没超过 2
两张图(本节主图 和 三条独立边)各算一次近似比,用整数表示(放大 100 倍),再验一次两者都没超过 2 倍。
⚠️ 最优要试多少个子集
暴力求最优要一个个试子集。数一数它试了多少个、贪心只看了多少条边,再算出七个点一共有多少个子集。
把 A 归到 B,是在做什么
"把问题 A 归约到问题 B"的意思是【0】。
⚠️ 归约的方向能不能反过来
已知 B 有快算法,你把 A 归约到 B,于是 A 也能快速解。要是方向反过来(把 B 归约到 A),得到的结论是【0】。
三个数组,各能不能分成两半
"划分问题":能不能把一个数组分成两堆,两堆的和相等?三个数组 [17, 24, 15, 13, 23]、[10, 20, 15, 5]、[17, 24, 15, 13, 23, 3] 各判一次。注意 can_split
自己写:把划分归约到子集和
subset_sum 已经有了(l1_algo_10 学过的那一套)。把"划分问题"翻译过去——一行新算法都不许写。
⚠️ 有些情况根本不用跑算法
三个数组各判一次,数一数 subset_sum 真正被调用了几次。(和是奇数的那个,一眼就能否掉,不该占一次调用。)
交付:归约做成了没有,看三件事
一次归约算不算做成,验三件事:答案对、没写新算法、两者同时成立。