具有什么性质的问题适合贪心策略求解？
题目
具有什么性质的问题适合贪心策略求解？
相似考题
参考答案和解析
正确答案:
具有如下性质：
第一、最优子结构性质；
第二、贪心选择性质。
第一、最优子结构性质；
第二、贪心选择性质。
更多“具有什么性质的问题适合贪心策略求解？”相关问题
-
第1题：
用贪心法求解的问题有什么特点参考答案：具备最优子结构。
-
第2题：
在求解某问题时，经过分析发现该问题具有最优子结构性质，若定义问题的解空间，以深度优先的方式搜索解空间，则采用（ ）算法设计策略。A.动态规划
B.贪心
C.回溯
D.分支限界答案：C解析：分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。
动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。
贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。
回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。
题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。 -
第3题：
什么是层次分析法？它适合求解什么问题？
正确答案: 层次分析法是美国匹兹堡大学萨蒂教授于20世纪70年代提出的特定性分析与定量分析相结合的多目标决策方法。此法把决策问题按总目标、各层子目标、评价准则直至具体的备选方案的顺序分解为不同的层次结构，然后利用求判断矩阵特征向量的办法，求得每一层次的各元素对上一层次某元素的优先权重，最后再用加权和的方法递阶归并各备选方案对总目标的最终权重，此最终权重值最大者即为层优方案。这里所谓“优先权重”是一种相对的量度，它表明各备选方案在某一特点的评价准则或子目标下优越程序的相对量度，以及各子目标对上一层目标（或总目标）而言重要程度的相对量度。层次分析法特别适宜于具有分层交错的目标系统，而且目标值又难以定量描述的决策问题。 -
第4题：
具有什么特征的问题适合用分治策略求解？
正确答案: 三个特征：
（1）原问题可以分解成规模较小、相互独立和类型相同的子问题；
（2）子问题的规模缩小到一定的程度，就不需要再分解，可以容易地求解；
（3）所有子问题的解能够合并成原问题的解。 -
第5题：
问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。
正确答案:最优子结构性质 -
第6题：
一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。
- A、重叠子问题
- B、最优子结构性质
- C、贪心选择性质
- D、定义最优解
正确答案:B -
第7题：
能采用贪心算法求最优解的问题，一般具有的重要性质为：（）
- A、最优子结构性质与贪心选择性质
- B、重叠子问题性质与贪心选择性质
- C、最优子结构性质与重叠子问题性质
- D、预排序与递归调用
正确答案:A -
第8题：
问答题具有什么特征的问题适合用分治策略求解？正确答案： 三个特征：
（1）原问题可以分解成规模较小、相互独立和类型相同的子问题；
（2）子问题的规模缩小到一定的程度，就不需要再分解，可以容易地求解；
（3）所有子问题的解能够合并成原问题的解。解析： 暂无解析 -
第9题：
填空题许多可以用贪心算法求解的问题一般具有2个重要的性质：（）性质和（）性质。正确答案： 贪心选择,最优子结构解析： 暂无解析 -
第10题：
填空题问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。正确答案： 最优子结构性质解析： 暂无解析 -
第11题：
问答题具有什么性质的问题适合贪心策略求解？正确答案： 具有如下性质：
第一、最优子结构性质；
第二、贪心选择性质。解析： 暂无解析 -
第12题：
问答题一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？正确答案： 按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解。解析： 暂无解析 -
第13题：
对于本题的作业处理问题，用图4-1的贪心算法策略，能否求得最高收益?(6)。用贪心算法求解任意给定问题时，是否一定能得到最优解?(7)。
正确答案：(6)能或可以、行及其他含义相同的词语 (7)不能或不可以、不行及其他含义相同的词语
(6)能，或可以、行及其他含义相同的词语 (7)不能，或不可以、不行及其他含义相同的词语 解析：本题考查的是算法的设计和分析技术。
问题1考查的是贪心算法的流程图。第(1)空表示第2个作业到第n个作业的主循环，i是循环控制变量，故第(1)空填入i<=n。
应注意到数组／中的作业J[i](1≤i≤k)是在其期限之前完成的作业，且d[J[i]]≤d[J[i+1]] (1≤id[i]。另一方面， J[D[R]]与r的关系只有两种：J[d[r]]>r，表示还可能在J[1]与J[r]之间插入作业i；J[d[r]]=r，表示不可能在J[1]～J[r]之间插入作业i。J[d[r]]问题2是本题算法的一个实例。6个作业的收益已经按降序排好序。根据流程图，将作业1，2，4和5放入数组J中，并得到总收益为220，具体过程如表4-1所示。
问题3考查算法策略。对于该题，贪心策略可以求得最优解。但不是所有的问题都能通过贪心策略来求得最优解，一个典型的例子是0-1背包问题。举例如下，有三件物品，背包可容纳50磅重的东西，每件物品的详细信息如表4-2所示，问如何装包使得其价值最大?
如果按贪心策略求解该问题，优先选择单位价值最大的物品，则先选择物品1，然后选择物品2。由于此时背包容量还剩下50-10-20=20，不足以容纳物品3，故总价值为 60+100=160美元。但若选择物品2和物品3，容量总和为20+30，小于等于总容量50，得到总价值为100+120=220，会得到更优解。此时用贪心策略不能得到最优解。 -
第14题：
在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用（ ）算法设计策略A.分治
B.动态规划
C.贪心
D.回溯答案：B解析：分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。
动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。
贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。
题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。 -
第15题：
对于0－1背包问题和背包问题的解法，下面（）答案解释正确。
- A、0－1背包问题和背包问题都可用贪心算法求解
- B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
- C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
- D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解
正确答案:C -
第16题：
具有什么性质的问题适合动态规划策略求解？
正确答案: 具有如下性质：
第一、最优子结构性质；
第二、子问题重叠性质。 -
第17题：
一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？
正确答案:按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解。 -
第18题：
动态规划算法的基本要素为（）
- A、最优子结构性质与贪心选择性质
- B、重叠子问题性质与贪心选择性质
- C、最优子结构性质与重叠子问题性质
- D、预排序与递归调用
正确答案:C -
第19题：
许多可以用贪心算法求解的问题一般具有2个重要的性质：（）性质和（）性质。
正确答案:贪心选择；最优子结构 -
第20题：
单选题动态规划算法的基本要素为（）A最优子结构性质与贪心选择性质
B重叠子问题性质与贪心选择性质
C最优子结构性质与重叠子问题性质
D预排序与递归调用
正确答案： C解析： 暂无解析 -
第21题：
单选题一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。A重叠子问题
B最优子结构性质
C贪心选择性质
D定义最优解
正确答案： C解析： 暂无解析 -
第22题：
问答题具有什么性质的问题适合动态规划策略求解？正确答案： 具有如下性质：
第一、最优子结构性质；
第二、子问题重叠性质。解析： 暂无解析 -
第23题：
问答题什么是层次分析法？它适合求解什么问题？正确答案： 层次分析法是美国匹兹堡大学萨蒂教授于20世纪70年代提出的特定性分析与定量分析相结合的多目标决策方法。此法把决策问题按总目标、各层子目标、评价准则直至具体的备选方案的顺序分解为不同的层次结构，然后利用求判断矩阵特征向量的办法，求得每一层次的各元素对上一层次某元素的优先权重，最后再用加权和的方法递阶归并各备选方案对总目标的最终权重，此最终权重值最大者即为层优方案。这里所谓“优先权重”是一种相对的量度，它表明各备选方案在某一特点的评价准则或子目标下优越程序的相对量度，以及各子目标对上一层目标（或总目标）而言重要程度的相对量度。层次分析法特别适宜于具有分层交错的目标系统，而且目标值又难以定量描述的决策问题。解析： 暂无解析