试题详情

试题内容

阅读下列说明和C代码，回答问题1至问题3。
【说明】
0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1...i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。
0-1背包问题具有最优子结构性质。定义c[i][T]为最优装包方案所获得的最大价值，则可得到如下所示的递归式。

【c代码】
下面是算法的C语言实现。
(1)常量和变量说明
T: 背包容量
v[]:价值数组
w[]:重量数组
c[][]:c[i][j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值
(2) C程序

【问题1】 (8分)
根据说明和C代码，填充C代码中的空(1) ~ (4)。
【问题2】 (4分)
根据说明和C代码，算法采用了 (5) 设计策略。在求解过程中，采用了（6）
(自底向上或者自顶向下)的方式。
【问题3】 (3分)
若5项物品的价值数组和重量数组分别为v[]= {0,1,6,18,22,28}和w[]= {0,1,2,5,6,7}背包容量为T= 11,则获得的最大价值为 (7)。

软题库参考答案：暂时没有答案（仅供参考）

软题库解析：正在加载....

你可能感兴趣的试题

第2题：阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
某企业拟构建一个高效、低成本、符合企业实际发展需要的办公自动化系统。工程师小李主要承担该系统的公告管理和消息管理模块的研发工作。公告管理模块的主要功能包括添加、修改、删除和查看公告。消息管理模块的主要功能是消息群发。
小李根据前期调研和需求分析进行了概念模型设计，具体情况分述如下：
【需求分析结果】
（1）该企业设有研发部、财务部、销售部等多个部门，每个部门只有一名部门经理，有多名员工，每名员工只属于一个部门，部门信息包括：部门号、名称、部门经理和电话，其中部门号唯一确定部门关系的每一个元组。
（2）员工信息包括：员工号、姓名、岗位、电话和密码。员工号唯一确定员工关系的每一个元组；岗位主要有经理、部门经理、管理员等，不同岗位具有不同的权限。一名员工只对应一个岗位，但一个岗位可对应多名员工。
（3）消息信息包括：编号、内容、消息类型、接收人、接收时间、发送时间和发送人。其中（编号，接收入）唯一标识消息关系中的每一个元组。一条消息可以发送给多个接收第3题：

试题三
阅读下列说明和UML图，回答问题1至问题4。
[说明]
某企业为了方便员工用餐，为餐厅开发了一个订餐系统(COS：Cafeteria Ordering System)，企业员工可通过企业内联网使用该系统。
企业的任何员工都可以查看菜单和今日特价。
系统的顾客是注册到系统的员工，可以订餐(如果未登录，需先登录)、注册工资支付、预约规律的订餐，在特殊情况下可以覆盖预订。
餐厅员工是特殊顾客，可以进行备餐、生成付费请求和请求送餐，其中对于注册工资支付的顾客生成付费请求并发送给工资系统。
菜单管理员是餐厅特定员工，可以管理菜单。
送餐员可以打印送餐说明，记录送餐信息(如送餐时间)以及记录收费(对于没有注册工资支付的顾客，由送餐员收取现金后记录)。
顾客订餐过程如下：
1．顾客请求查看菜单：
2．系统显示菜单和今日特价；
3．顾客选菜；
4．系统显示订单和价格；
5．顾客确认订单；
6．系统显示可送餐时间；
7．顾客指定送第6题：阅读下列说明和Java代码，将应填入（n）处的字句写在答题纸的对应栏内。
【说明】
某咖啡店当卖咖啡时，可以根据顾客的要求在其中加入各种配料，咖啡店会根据所加入的配料来计算费用。咖啡店所供应的咖啡及配料的种类和价格如下表所示。

第3题：阅读下列说明和UML图，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】
某企业为了方便员工用餐，餐厅开发了一个订餐系统（COS：Cafeteria Ordering System），企业员工可通过企业内联网使用该系统。
企业的任何员工都可以查看菜单和今日特价。
系统的顾客是注册到系统的员工，可以订餐（如果未登录，需先登录）、注册工资支付、预约规律的订餐，在特殊情况下可以覆盖预订。
餐厅员工是特殊顾客，可以进行备餐、生成付费请求和请求送餐，其中对于注册工资支付的顾客生成付费请求并发送给工资系统。
菜单管理员是餐厅特定员工，可以管理菜单。
送餐员可以打印送餐说明，记录送餐信息（如送餐时间）以及记录收费（对于没有注册工资支付的顾客，由送餐员收取现金后记录）。
顾客订餐过程如下：
1．顾客请求查看菜单；
2．系统显示菜单和今日特价；
3．顾客选菜；
4．系统显示订单和价格；
5．顾客确认订单；
6．系统显示可送餐时间；
7．顾客指定送第4题：

试题四
设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案是的完成所有任务所需要的时间最短。
假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个1务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。
[C代码]
下面是算法的C语言实现。
10常量和变量说明
m:机器数。
n:任务数。
t[]：输入数组，长度为n，其中每个元素表示任务的运行时间，下标从0开始。
s[][]:二维数组，长度为m*n，下标从0开始，其中元素s[i][j]表示机器i运行的任务j的编号。
d[]：数组，长度为m其中元素d[i]表示机器i的运行时间，下标从0开始。
count[]:数组，长度为m，下标从0开始，其中元素count[i]表示机器i运行的任务数。
i：循环变量。
j：循环变量。
k：临时变量。
max：完成所有任务的时间。
min：临时变量。
第1题：阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
某慈善机构欲开发一个募捐系统，已跟踪记录为事业或项目向目标群体进行募捐而组织的集体性活动。该系统的主要功能如下所述。
（1）管理志愿者。根据募捐任务给志愿者发送加入邀请、邀请跟进、工作任务；管理志愿者提供的邀请响应、志愿者信息、工作时长、工作结果等。
（2）确定募捐需求和收集所募捐赠（资金及物品）。根据需求提出募捐任务、将活动请求和捐赠请求，获取所募集的资金和物品。
（3）组织募捐活动。根据活动请求，确定活动时间范围。根据活动时间，搜索场馆，即：向场馆发送场馆可用性请求，获得场馆可用性。然后根据活动时间和地点推广募捐活动，根据相应的活动信息举办活动，从募捐机构获取资金并向其发放赠品。获取和处理捐赠，根据捐赠请求，提供所募集的捐赠；处理与捐赠人之间的交互，即：
录入捐赠人西悉尼，处理后存入捐赠人信息表；从捐赠人信息表中查询捐赠人信息，向捐赠人发送捐赠请求，并将已联系的捐赠人存入已联系的捐赠人表。根据捐赠请求进行募集，募得捐赠后，将捐赠记录存入捐赠表；

咖啡	价格/杯	配料	价格/份
蒸馏咖啡（Espresso）	25	摩卡（Mocha）	10