阅读下列程序说明和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题:
第2题:
第3题:
第4题:
第5题:
试题三(共 15 分)
阅读以下说明和 C 程序,将应填入 (n) 处的字句写在答题纸的对应栏内。
第6题:
阅读下列程序说明和C++程序,把应填入其中(n)处的字句,写在对应栏内。
【说明】
阅读下面几段C++程序回答相应问题。
比较下面两段程序的优缺点。
①for (i=0; i<N; i++ )
{
if (condition)
//DoSomething
…
else
//DoOtherthing
…
}
②if (condition) {
for (i =0; i<N; i++ )
//DoSomething
}else {
for (i=0; i <N; i++ )
//DoOtherthing
…
}
第7题:
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。
[说明]
背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。
背包问题是一个典型的NP完全难题。对该问题求解方法的研究无论是在理论上,还是在实践中都具有一定的意义。如管理中的资源分配、投资决策、装载问题等均可建模为背包问题。
常用的背包问题求解方法很多,但本题中采用了一种新的算法来求解背包问题。该算法思想为:首先要对物品进行价重比排序,然后按价重比从大到小依次装进包裹。这种方法并不能找到最佳的方案,因为有某些特殊情况存在,但只要把包中重量最大的物品取出,继续装入,直到达到limitweight,这时的物品就是limit weight的最大价值。这种算法不需要逐个进行试探,所以在数据非常大时,执行效率主要由排序的时间复杂度决定。该算法的流程图为图11-4。
仔细阅读程序说明和C程序流程图及源码,回答问题1和问题2。
[流程图11-4]
[程序说明]
struct Thing:物品结构
typedef struct Bag:背包结构类型
input ( ):将物品按序号依次存入数组函数
inbag ( ):物品按物价比入包函数
init ( ):初始化函数
sort ( ):对物品按价格重量比排序函数
outbag ( ):取出包中weiht最大的物品函数
print ( ):最佳方案输出函数
[C程序]
define N 255
struct Thing {
double weight;
double value;
double dens;
}thing[N];
typedef stmct Bag {
Thing thing [N];
double weighttmp;
double sumvalue;
}bag,best;
inbag ( )
{
do{
bag.thing[i]=thing[i]
(1)
(2)
i++;
}while ( (3) )
}
init ( )
{
for (inti=0; i<N; i++)
{
input (thing[i].weight, thing [i].value)
thing [i].dens=thing[i].value/thing [i].weight;
};
}
main ( )
{
init ( );
sort ( );
inbag ( );
do {
best=bag; //把包中物品放入暂存数组
outbag ( ); //取出包中weight最大的物品
(4)
}while ( (5))
print (best); //输出temp因为是最佳方案
}
根据程序说明及流程图、部分C源码,充分理解算法思想,填入(n)处。
第8题:
阅读下列程序说明和C代码,将应填入(n)处的字句写在对应栏内。
【说明】
“背包问题”的基本描述是:有一个背包,能盛放的物品总重量为S,设有N件物品,其重量分别为w1,w2,…,wn。希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品的重量之和等于S。
如下程序均能求得“背包问题”的一组解,其中程序1是“背包问题”的递归解法,而程序2是“背包问题”的非递归解法。
【程序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)){/*考虑物品n被选择的情况*/
printf("%4d",w[n]);
return 1;
}
return (2);/*考虑不选择物品n的情况*/
}
main()
{
if(knap(S,N))printf("OK!\n");
else printf("N0!\n");
}
【程序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("0K!\n");
else printf("N0!\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=1; 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;
}
}/*while*/
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*/
}/*while*/
}/*if*/
/*while*/
if(k){&nbs
第9题:
●试题四
阅读下列程序说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。
【程序4.1说明】
"背包问题"的基本描述是:有一个背包,能盛放的物品总重量为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(″N0!\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=l;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"。