简答题

简述找零问题、背包问题与贪婪算法。

正确答案

设有不同面值的钞票，要求用最小数量的钞票给顾客找某数额的零钱，这就是通常说的找零问题。
给定n种物品和一个背包，设Wi为物品i的重量，V_i为其价值，C为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物品总价最大，这就是背包问题。
贪婪算法是一种传统的启发式算法，它采用逐步构造最优解的方法，即在算法的每个阶段，都作出在当时看上去最好的决策，以获得最大的“好处”，换言之，就是在每一个决策过程中都要尽可能的“贪”，直到算法中的某一步不能继续前进时，算法才停止。在算法的过程中，“贪”的决策一旦作出，就不可再更改，作出“贪”的决策的依据称为贪婪准则。贪婪算法是从局部的最优考虑问题的解决方案，具有简单快捷的优点。但是，这种从局部，而不是从整体最优上考虑问题的算法，并不能保证求得的最后解为最优解。

答案解析

略

相似试题

下列算法中不能解决0/1背包问题的是（）
单选题查看答案
背包问题的贪心算法所需的计算时间为（）
单选题查看答案
0-1背包问题的回溯算法所需的计算时间为（）
单选题查看答案
背包问题的贪心算法。横线处填（）
填空题查看答案
在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明算法的正确性）
简答题查看答案
一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？
简答题查看答案
用动态规划算法解0-1背包问题：n=5，w=[2，9，4，6，7]，p=[6，10，12，8，13]，c=15。
简答题查看答案
对于0－1背包问题和背包问题的解法，下面（）答案解释正确。
单选题查看答案
关于0－1背包问题以下描述正确的是（）
单选题查看答案

语音搜题

拍照搜题

打赏

计算机科学

简述找零问题、背包问题与贪婪算法。

正确答案

答案解析