大学选修课

单选题选择背包可根据（）来选择不同功能的背包。A 活动内容和性质B 个人喜好C 活动时长D 个人身高

题目
单选题
选择背包可根据（）来选择不同功能的背包。
A

活动内容和性质

B

个人喜好

C

活动时长

D

个人身高

如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

考虑下述背包问题的实例。有5件物品，背包容量为100,每件物品的价值和重量如下表所示，并已经按照物品的单位重量价值从大到小徘好序，根据物品单位重量价值大优先的策略装入背包中，则采用了（ ）设计策略。考虑0/1背包问题（每件物品或者全部放入或者全部不装入背包）和部分背包问题（物品可以部分装入背包），求解该实例，得到的最大价值分别为（请作答此空）。

A.605和630
B.605和605
C.430和630
D.630和430

答案：C
解析：
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。0/1背包考虑该问题时，只能放入1、2、3号物品，故总价值为430,采用部分背包问题可以将物品拆分，故放1、2、3号物品后还可以放入部分4号物品，故总容量为630。

第2题：

皮包的选择也要注意与服饰搭配的选择，下面说法不正确的是（）。

  • A、夏季应选择小巧的包
  • B、注意和服饰的搭配
  • C、冬季应选择深色的包
  • D、出门郊游可以选择体积大的背包

正确答案:D

第3题：

*部分背包问题可有贪心法求解：计算Pi/Wi

数据结构：

w[i]:第i个背包的重量；

p[i]:第i个背包的价值；

1．0-1背包： 每个背包只能使用一次或有限次(可转化为一次)：

A.求最多可放入的重量。


正确答案：

 

NOIP2001 装箱问题
有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
l 搜索方法
procedure search(k,v:integer); {搜索第k个物品，剩余空间为v}
var i,j:integer;
begin
if v<best then best:=v;
if v-(s[n]-s[k-1])>=best then exit; {s[n]为前n个物品的重量和}
if k<=n then begin
if v>w[k] then search(k+1,v-w[k]);
search(k+1,v);
end;
end;

l DP
F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。
实现:将最优化问题转化为判定性问题
f [I, j] = f [ i-1, j-w[i] ] (w[I]<=j<=v) 边界：f[0,0]:=true.
For I:=1 to n do
For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]];
优化：当前状态只与前一阶段状态有关，可降至一维。
F[0]:=true;
For I:=1 to n do begin
F1:=f;
For j:=w[I] to v do
If f[j-w[I]] then f1[j]:=true;
F:=f1;
End;

第4题：

关于0－1背包问题以下描述正确的是（）

  • A、可以使用贪心算法找到最优解
  • B、能找到多项式时间的有效算法
  • C、使用教材介绍的动态规划方法可求解任意0－1背包问题
  • D、对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题

正确答案:D

第5题：

选择背包可根据（）来选择不同功能的背包。 

  • A、活动内容和性质
  • B、个人喜好
  • C、活动时长
  • D、个人身高

正确答案:A

第6题：

坐公交时怎样防止扒窃？（）

  • A、背包放在身后
  • B、时刻盯着背包看
  • C、上下车背包抱在胸前

正确答案:C

第7题：

选择背包、要根据个人（）选择背负系统。

  • A、身高
  • B、躯干长度
  • C、腿长
  • D、臂长

正确答案:B

第8题：

考虑下述背包问题的实例。有5件物品，背包容量为100,每件物品的价值和重量如下表所示，并已经按照物品的单位重量价值从大到小徘好序，根据物品单位重量价值大优先的策略装入背包中，则采用了（请作答此空）设计策略。考虑0/1背包问题（每件物品或者全部放入或者全部不装入背包）和部分背包问题（物品可以部分装入背包），求解该实例，得到的最大价值分别为（ ）。

A.分治
B.贪心
C.动态规划
D.回溯

答案：B
解析：
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。0/1背包考虑该问题时，只能放入1、2、3号物品，故总价值为430,采用部分背包问题可以将物品拆分，故放1、2、3号物品后还可以放入部分4号物品，故总容量为630。

第9题：

有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背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），单位重量物品价值（7.5，2.67，1.5，0.8，0.375，0.1）


正确答案: 可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。
1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。
2.把重量为3的物品放进背包，此时剩余载重量为14，P为23；
3.把重量为4的物品放进背包，此时剩余载重量为10，P为29；
4.把重量为5的物品放进背包，此时剩余载重量为5，P为33；
由于8>5，所以不能再放进背包。
结果是把重量为2，3，4，5的物品装进背包，总价值最大为33。

第10题：

对于0－1背包问题和背包问题的解法，下面（）答案解释正确。

  • A、0－1背包问题和背包问题都可用贪心算法求解
  • B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
  • C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
  • D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解

正确答案:C

更多相关问题
相关内容