算法设计与分析问答题每日一练(2019.04.21)

问答题
写出0/1背包问题的动态规划方程，并简要说明。
答案：
F_i（X）是前i个物品，背包容积X子问题的最优值，
当第i个物品不选入，f<...
问答题
简述动态规划算法的基本步骤。
答案：设计一个标准的动态规划算法，通常可按以下几个步骤进行：
（1）划分阶段：按照问题的时间或空间特征，把问题分为若...
问答题
有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？
答案：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4...
问答题
用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要花多少时间（要讲出道理）。
答案：至少需要对每个元素进行一次比较运算，运算时间是O（n）。
问答题
简述分支限界法及其算法思想。
答案：这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间...

首页

题库

网课

在线模考

桌面端

算法设计与分析问答题每日一练(2019.04.21)

写出0/1背包问题的动态规划方程，并简要说明。

简述动态规划算法的基本步骤。

用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要花多少时间（要讲出道理）。

简述分支限界法及其算法思想。