首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列程序说明和C++代码,将应填入(n)处。 【说明】 “背包问题”的基本描述是:有一个背包,能盛放的物品总重量为S,设有N件物品,其重量分别为w1;w2,……,wn,希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品
阅读下列程序说明和C++代码,将应填入(n)处。 【说明】 “背包问题”的基本描述是:有一个背包,能盛放的物品总重量为S,设有N件物品,其重量分别为w1;w2,……,wn,希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品
admin
2009-02-15
32
问题
阅读下列程序说明和C++代码,将应填入(n)处。
【说明】
“背包问题”的基本描述是:有一个背包,能盛放的物品总重量为S,设有N件物品,其重量分别为w1;w2,……,wn,希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品的重量之和等于S。
如下程序均能求得“背包问题”的一组解,其中程序4.1是“背包问题”的递归解法,而程序4.2是“背包问题”的非递归解法。
【程序4.1】
#include<stdio.h>
#define N 7
#define S 15
int w[N+1]={0,1,4,3,4,5,2,7};
int knap(int s,int n)
{ if(s==0)return 1;
if(s<0||(s>0& &n<1))return 0;
if((1)))|
printf("%4d",w[n]);return 1;
} return (2);
}
main(){
if(knap(S,N))printf("OK!\n");
else printf("NO!\n");
}
【程序4.2】
#include<stdio.h>
#define N 7
#define S 15
typedef struct{
int s;
int n:
int job;
} KNAPTP;
int w[N+1]={0,1,4,3,4,5,2,7};
int knap(int s,int n);
main(){
if(knap(S,N))printf("OK!\n");
else printf("NO!\n");}
int knap(int s,int n)
{ KNAPTP stack[100],x;
int top,k,rep;
x.s=s;x.n=n;
x.job=0;
top=|;Stack[top]=x;
k=0;
while((3)){
x=Stack[top];
rep=1;
while(!k && rep){
if(x.s==0)k=1;/*已求得一组解*/
else if(x.s<0||x.n <=0)rep=0;
else{x.s=(4);x.job=1;
(5)=x;
}
}
if(!k){
rep=1;
while(top>=1&&rep){
x=stack[top--];
if(x.job==1){
x.s+=W[x.n+1];
x.job=2;
Stack[++top]=x;
(6);
}
}
}
}
if(k){/*输出一组解*/
while(top>=1){
x=staCk[top--];
if(x.job==1)
printf("%d\t",w[x.n+1]);
}
}
return k;
}
选项
答案
(1)knap(s-w[n],n-1)(2)knap(s,n-1)(3)top>=1 && ! k 或 top>0 && k==0(4)x.s-w[x.n--](5)stack[++top](6)rep=0
解析
试题提供了两种解决问题的方法,程序5.1是用递归的方法来解决背包问题,程序5.2使用非递归的方法来解决背包问题。每次选择一个物品放入背包,那么剩余的物品和背包剩余的重量,又构成一个“背包问题”。程序从数组下标最大的物品开始考查,因此(1)处应该填“knap(s-w[n],n-1)”,即将数组中第N个物品放入背包,如果它能够放入到背包中,则该物品是构成解的元素之一;否则,将该物品从背包中取出,该物品不构成解的元素,在以后的考查中,它可以被排除,因此(2)处应该填“knap(s,n-1)”。在改程序中用栈来保存已经考查过的物品,结构KNAPTP表示经过考查的物品,s表示考查过该物品后背包所能够盛放的物品的重量;n表示该物品在数组W中的下标;job表示物品当前的状态:当job等于1,表示物品n可以放入背包; job等于2表示物品n不能被放入到背包,那么在以后的选取中将不再考虑该物品。初始时job等于0,表示背包中没有任何放入任何物品。 K为有解的标志。Rep为一个标志变量,rep等于0,表示结束当前的动作;rep等于1表示继续进行当前的动作。当栈顶物品不能放入背包时,将rep设置为0,表示下一步不从数组w中取物品。其初值为1。开始时,将数组中下标最大的物品放入栈中,然后开始考查该物品。该物品满足放入背包的条件,第(4)(5)空将完成将物品放入背包的操作,因此(4)空填“x.s-w[x.n--]”,修改背包的可容纳物品的重量; (5)处填"stack[++top]",将下一个要考查的物品放入栈中。若该物品不满足放入背包的条件,则将该物品从背包中取出,因此将rep置为 0,结束循环while(! k&&rep)。将物品从背包中取出,即释放该物品在背包中所占的重量,并标记为不能放入到背包(job=2),再将其放入到栈中;然后继续考查数组w中的下一个物品,因此需要结束循环while (top>=1 &&rep),将rep置为0,所以第(6)处应该填“rep=0”。在第三处要求给出循环结束的条件,即可以继续选取物品的条件,在此处填“top>=1&&!k”。
转载请注明原文地址:https://kaotiyun.com/show/EwDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。“建立风险条目检查表”是(18)时的活动,“描述风险的结果”是(19)时的活动。
(14)以静态或动态的连接方式,为应用程序提供一组可使用的类。(15)除了提供可被应用程序调用的类以外,还基本实现了一个可执行的架构。
对“功能测试的回归测试经常要多次重复”的正确理解是(36)。
对于逻辑表达式((a&b)||c,需要______个测试用例才能完成条件组合覆盖。
模块设计中,某模块根据输入的控制信息从文件中读一个记录或者向文件中写一个记录,则其内聚类型为______。
王某是M国际运输有限公司计算机系统管理员。任职期间,王某根据公司的业务要求开发了“海运出口业务系统”,并由公司使用。随后,王某向国家版权局申请了计算机软件著作权登记,并取得了《计算机软件著作权登记证书》,证书明确软件名称是“海运出口业务系统V1.0”,著作
()过程模型明确地考虑了开发中的风险。
如下图所示,从输出的信息中可以确定的信息是___________。
以下关于用例图的叙述中,不正确的是(44)。图书馆管理系统需求中包含“还书”用例和“到书通知”用例,对于“还书”用例,应先查询该书是否有人预定,若有则执行“到书通知”。“还书”用例和“到书通知”用例是(45)关系,以下用例图中,(46)是正确的。管理员处
某教学管理数据库中,学生、课程关系模式和主键分别为:S(学号,姓名,性别,家庭住址,电话),关系S的主键为学号;C(课程号,课程名,学分),关系C的主键为课程号。假设一个学生可以选择多门课程,一门课程可以由多个学生选择。一旦学生选择某门课程必定有该课程的成
随机试题
FewwoulddisputethattheLansleyreformsoftheNationalHealthServiceinEngland,embodiedintheHealthandSocialCareAct
建设工程监理管理服务的内涵不包括()。
当事人一方有权请求人民法院或者仲裁机构变更或撤销的合同有( )。
股票和债券是直接投资工具,筹集的资金主要是投向实业领域;而证券投资基金是一种间接投资工具,所筹集的资金主要投向有价证券等金融工具。()
关于增长量的说法,正确的有()。
南海公司计划用新设备替换旧设备。旧设备预计尚可使用5年,目前变现净收入为60000元。新设备投资额为150000元,预计使用5年。至第5年末,新、旧设备的预计残值假设分别为10000元和6000元(各残值与税法的规定相同)。使用新设备可使企业在未来5年
电磁波属于横波,而不属于纵波。()
随着环境、教育和实践活动的作用,人的遗传素质会逐渐地发生变化。这说明遗传素质具有可塑性。()
我国的多党合作制是()。
[*]
最新回复
(
0
)