组合优化答案2023

第三章测试

1.设是取值在中的整变量，为0-1变量，“取值为1当且仅当”可用来表示。（ ）
A:错 B:对
答案:A
2.

考虑背包问题的下述算法，首先将物品按某种顺序排列，随后逐个放入背包，直至有物品不能放入背包时，算法终止。以下物品排列顺序，可使该算法的最坏情况比为有限常数的是（ ）。

A:其他选项都不是。
B:将物品按价值从大到小的顺序排列。
C:将物品按大小从大到小的顺序排列。
D:将物品按价值密度从大到小的顺序排列。

答案:A
3.某员工的购物车内有件商品，其中商品的价格为。定义为员工使用不超过的资金，仅考虑购买购物车中前件商品时所能购买的商品价格之和的最大值，则满足的递推关系为（ ）
A:。
B:。
C:。
D:。

答案:D
4.考虑下面的排序问题，现有两台机器和以及个工件。每个工件需先在上加工再在上加工后才能完工。工件在和上加工所需的时间分别为和，。一台机器在同一时刻只能加工一个工件。目标为最大工件完工时间尽可能小。该问题最优值的下界有（ ）。
A:
B:
C:
D:

答案:BC
5.设算法A为一极小化目标优化问题的近似算法，现用比较算法A给出的实例的可行解目标值和的方法证明算法A的最坏情况比，其中是实例的最优值的下界，满足对任意实例成立。以下说法正确的有（ ）。
A:算法A的最坏情况比可能小于。
B:可能存在，使得对任意实例，。
C:用上述方法，不可能证得算法A的最坏情况比小于。
D:可能存在，使得对任意实例，。

答案:ABC