K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
最优解构造与证明是算法设计的核心环节，常用证明方法包括交换论证、数学归纳法、反证法等，请结合相关知识判断下列表述的正误。
活动选择问题中，每次选择结束时间最早的兼容活动，可通过交换论证法证明该策略能得到全局最优解
用数学归纳法证明最优解时，仅需证明规模为k的问题的最优解可由规模为k-1的子问题的最优解推导得到即可
反证法证明最优解的核心思路是：假设存在比当前构造的解更优的解，推导该假设会产生矛盾，从而证明当前解是最优的
0-1背包问题无法用贪心策略得到全局最优，本质是贪心选择的局部最优无法通过交换论证推广到全局最优