给定序列X={A, B, C, B, D, A, B}和Y={B, D, C, A, B, A}，它们的最长公共子序列是（）。

A. BCBA
BCDA
C. BDAB
D. BCAA

有关动态规划描述正确的是()

A. 动态规划将多阶段决策问题转化为单阶段决策问题。
B. 动态规划往往用于求解某种最优性质的问题。
C. 适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。
D. 动态规划求解时往往采用填表的方法记录问题最优值。
E. 动态规划划分的各子问题与原问题相同,一般递归求解子问题。
F. 动态规划求解某种最优性质的问题时,整体的最优值和子问题的最优值之间存在递归关系。

动态规划的基本要素是()

A. 重叠子问题
B. 最优子结构性质
C. 自底向上的求解方式
D. 自顶向下的递归求解方式

规模为n的0-1背包问题,有关子问题描述正确的是()

A. 子问题可以描述为规模为i的0-1背包问题,即:1...i共i个物品,背包容量为j
B. 用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-wixi的最优值为c[i-1][j-wi]。
C. 用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-wixi的最优值为c[i-1][j-wixi],其中xi等0或1。
D. 用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-wixi的最优值为c[i-1][j]。

有关0-1背包问题,用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-wixi,以下说法正确的是()

A. 当i=0时或j=0时,c[i][j]=0。
B. 当j<wi时,物品无法装入,其xi=0,则背包容量依旧为j,c]i][j]=c[i-1][j].
C. 当j≥wi时,物品可以装入,装呢还是不装呢?这取决于哪个决策能够让c[i][j]最小。故c]i][j]=min(c[i-1][j],c[i-1][j-wi]+vi)
D. 当j≥wi时,物品可以装入,装呢还是不装呢?这取决于哪个决策能够让c[i][j]最大。故c]i][j]=max(c[i-1][j],c[i-1][j-wi]+vi)

针对最优性质的动态规划算法中，采用自底向上求解方法求解最优值的原因是（）。

最长公共子序列问题的动态规划算法中，第二步建立的最优值c[i][j]的递归关系式中，边界条件是（）

0-1背包问题的贪心法解法和动态规划解法都能够生成最优解。

A. 对
B. 错

最长公共子序列问题中，如果采取穷举法，可以在序列A中子序列可能的开头和结尾（因为子序列由其开头位置和结尾位置唯一确定），然后在序列B中查找它是否存在，如果按照子序列长度降序枚举，找到的第一个公共子序列就是最长公共子序列。

A. 对
B. 错

以传统动态规划求解0-1背包问题，背包容量可以是任意实数。

A. 对
B. 错