对于0-1背包问题和背包问题的解法,下面答案解释正确()
A.0-1背包问题和背包问题都可用贪心算法求解
B.0-1背包问题可用贪心算法求解,但背包问题则不能用贪心算法求解
C.0-1背包问题不能用贪心算法求解,但可用使用动态规划或搜索算法求解,而背包问题则可以用贪心算法求解
D.因为0-1背包问题不具有最优子结构性质,所以不能用贪心算法求解
A.0-1背包问题和背包问题都可用贪心算法求解
B.0-1背包问题可用贪心算法求解,但背包问题则不能用贪心算法求解
C.0-1背包问题不能用贪心算法求解,但可用使用动态规划或搜索算法求解,而背包问题则可以用贪心算法求解
D.因为0-1背包问题不具有最优子结构性质,所以不能用贪心算法求解
第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("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;
}
第2题
阅读下列程序说明和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;
}
第3题
A、若用贪心算法解决0-1背包问题,只能得到近似最优解
B、若用贪心算法解决部分背包问题,只能得到近似最优解
C、在0-1背包问题中,物品只有装入和不装入两种情况,而部分背包问题允许只装入物品的一部分
D、没有区别,它们的含义相同
第4题
二维0-1背包问题:给定n种物品和一个背包。物品i的重量是,体积是,价值为,每种物品只有1个。背包的重量限制为W,容积限制为V。问如何选择装入背包的物品,使得背包物品的总价值最大? 设表示使用前i种物品、背包重量限制为j、容积为k时的最大价值,其中那么递推方程是:
A、
B、
C、
D、
第5题
二维0-1背包问题:给定n种物品和一个背包。物品i的重量是,体积是,价值为,每种物品只有1个。背包的重量限制为W,容积限制为V。 设表示使用前i种物品、背包重量限制为j、容积为k时的最大价值,其中那么递推方程是:考虑上述的二维0-1背包问题,动态规划算法的时间复杂度是:
A、
B、
C、
D、
E、
第6题
二维0-1背包问题:给定n种物品和一个背包。物品i的重量是,体积是,价值为,每种物品只有1个。背包的重量限制为W,容积限制为V。问如何选择装入背包的物品,使得背包物品的总价值最大? 设表示使用前i种物品、背包重量限制为j、容积为k时的最大价值,其中那么递推方程是:
A、
B、
C、
D、
第9题
下面给出了0-1背包问题的动态规划算法伪代码,其中空白处应分别填入____ 输入:商品数量,各商品价值,各商品体积,背包容量输出:商品价格的最大值,最优解方案 创建二维数组fordoend fordo end fordo for do ifthenend elseend end endfor do ifthen print 选择商品end else print 不选择商品 end end return,
A、
B、
C、
D、
第10题
A、使用约束函数剪去不合理的左子树(装该物品)。
B、使用限界函数剪去得不到更优解的左子树(装该物品)。
C、使用约束函数剪去不合理的右子树(不装该物品)。
D、使用限界函数剪去得不到更优解的右子树(不装该物品)。
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!