第1题:
本题考查贪心算法和背包问题的知识点。
分治:分治策略通常是将问题分解成若干个子问题,递归地解决这些子问题,然后将子问题的解合并以得到原问题的解。在这个背包问题中,并没有明显地将问题分解成子问题的过程,因此这不是分治策略。
贪心:贪心策略是在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。在这个背包问题中,按照单位重量价值从大到小排序并优先装入,正是贪心策略的体现,因为它在每一步都选择了当前看来最优的物品装入背包。
动态规划:动态规划通常用于解决具有重叠子问题和最优子结构的问题。它通过将原问题分解为相对简单的子问题的方式求解复杂问题。在这个背包问题中,虽然动态规划是一个可能的解决方案(特别是当需要考虑所有可能的物品组合时),但题目描述的策略并不符合动态规划的特点。
回溯:回溯算法通过探索所有可能的候选解来找出所有的解。如果候选解被确认不是一个解(或者至少不是最后一个解),回溯算法会通过在上一步进行一些变化来丢弃该解,即“回溯”并通过不同的路径来搜索解空间。在这个背包问题中,并没有使用回溯算法来搜索所有可能的解,而是采用了贪心策略来直接寻找一个解。
0/1背包考虑该问题时,只能放入1、2、3号物品,故总价值为430,采用部分背包问题可以将物品拆分,故放1、2、3号物品后还可以放入部分4号物品,故总容量为630。
综上所述,本题选择BC选项。
第2题: