下载APP
【单选题】
利用贪心法求解0/1背包问题时，(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时，将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X)，设fi(x)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为 wj和pj(j=1～n)。则依次求解f0(x)、f1(x)、...、fn(X)的过程中使用的递推关系式为(56)。.
A.
fi(X)=min{fi-1(X),fi-1(X)+pi}
B.
fi(X)=max{fi-1(X),fi-1(X-Wi)+pi
C.
fi(X)=min{fi-1(X-wi),fi-1(X-wi)+pi}
D.
fi(X)=max{fi-1(X-wi),fi-1(X)+pi}
参考答案：
参考解析：
刷刷题刷刷变学霸
举一反三
【单选题】以下对背包问题最优解的描述，正确的是（ ）
A.
对于离散形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。
B.
对于连续形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。
C.
对于连续形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。
D.
对于离散形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。
【单选题】设某算法的计算时间表示为递推关系式T（n）＝T（n-1）+n（n＞O）及T（0）＝1，则该算法的时间复杂度为（）。
A.
O(lgn)
B.
O(nlgn)
C.
O(n)
D.
O(n2)
【单选题】（22）处填（）。 A．分治法 B．贪心法 C．动态规划方法 D．回溯法
A.
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是 (21) ，该算法采用的设计方法是 (22) 。
【单选题】某递归算法的执行时间的递推关系如下: T(n)=1 当 n=1 时 T(n)=T(n/2)+1 当 n>1 时 则该算法的时间复杂度为( )。
A.
o(1)
B.
o( )
C.
o(n)
D.
o( )
【单选题】利用贪心法求解0/1背包问题时，(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时，将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X)，设fi(x)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为 wj和pj(j=1～n)。则依次求解f0(x)、f1(x)、...、fn(X)的过程中使用的递推关系式为(56)。.
A.
fi(X)=min{fi-1(X),fi-1(X)+pi}
B.
fi(X)=max{fi-1(X),fi-1(X-Wi)+pi
C.
fi(X)=min{fi-1(X-wi),fi-1(X-wi)+pi}
D.
fi(X)=max{fi-1(X-wi),fi-1(X)+pi}
【单选题】某递归算法的执行时间的递推关系如下：T(n)=1 当n=1时T(n)=2T(n/2)+1 当n>1时则该算法的时间复杂度为( )。
A.
O(1)
B.
O(log2n)
C.
O(n)
D.
O(nlog2n)
相关题目：
【单选题】分枝限界法求解 0/1 背包问题时,活结点表的组织形式是( )。
A.
小根堆
B.
大根堆
C.
栈
D.
数组
【判断题】连续背包问题可以用单纯形法来解决。
A.
正确
B.
错误
【单选题】动态规划方法的缺点之一是“维数灾”问题，对于多维多阶段决策问题，可采用的方法不包括：
A.
拉格朗日乘数法
B.
逐次逼近法
C.
粗格子点法
D.
蒙特卡洛法
【单选题】以下对背包问题最优解的描述，正确的是（ ）
A.
对于离散形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。
B.
对于连续形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。
C.
对于连续形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。
D.
对于离散形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。
【多选题】动态规划的标准型是由（）部分构成的
A.
非负条件
B.
目标要求
C.
基本方程
D.
约束条件
【单选题】背包问题与0-1背包问题的有很大差异,以下描述错误的是
A.
装包方式不同
B.
求解目标不同
C.
约束条件相同
D.
算法和结果不同
【判断题】多阶段决策之间的递推关系依赖于每个阶段的最优值。
A.
正确
B.
错误
【单选题】Pell方程的解构成数列,,则，满足以下哪个递推关系式？
A.
B.
C.
D.
【单选题】设某算法的计算时间表示为递推关系式T（n）＝T（n-1）+n（n＞O）及T（0）＝1，则该算法的时间复杂度为（）。
A.
O(lgn)
B.
O(nlgn)
C.
O(n)
D.
O(n2)
【单选题】（22）处填（）。 A．分治法 B．贪心法 C．动态规划方法 D．回溯法
A.
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是 (21) ，该算法采用的设计方法是 (22) 。
【单选题】某递归算法的执行时间的递推关系如下: T(n)=1 当 n=1 时 T(n)=T(n/2)+1 当 n>1 时 则该算法的时间复杂度为( )。
A.
o(1)
B.
o( )
C.
o(n)
D.
o( )
【单选题】背包问题是以下哪种优化模型？
A.
有约束非线性规划
B.
0-1规划
C.
无约束非线性规划
D.
线性规划
【单选题】利用贪心法求解0/1背包问题时，(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时，将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X)，设fi(x)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为 wj和pj(j=1～n)。则依次求解f0(x)、f1(x)、...、fn(X)的过程中使用的递推关系式为(56)。.
A.
fi(X)=min{fi-1(X),fi-1(X)+pi}
B.
fi(X)=max{fi-1(X),fi-1(X-Wi)+pi
C.
fi(X)=min{fi-1(X-wi),fi-1(X-wi)+pi}
D.
fi(X)=max{fi-1(X-wi),fi-1(X)+pi}
【单选题】某递归算法的执行时间的递推关系如下：T(n)=1 当n=1时T(n)=2T(n/2)+1 当n>1时则该算法的时间复杂度为( )。
A.
O(1)
B.
O(log2n)
C.
O(n)
D.
O(nlog2n)