网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6,3，5，4，6}，求背包问题的最大装包价值。若此为0-1背包问题，分析该问题具有最优子结构，定义递归式为
其中c(i，j)表示i个物品、容量为j的0-1背包问题的最大装包价值，最终要求解c(n,W)。 采用自底向上的动态规划方法求解，得到最大装包价值为(62)，算法的时间复杂度为(63)。 若此为部分背包问题，首先采用归并排序算法，根据物品的单位重量价值从大到小排序，然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量，则得到的最大装包价值为(64)，算法的时间复杂度为(65)。
A.11
B.14
C.15
D.16.67
参考答案
更多 “ 考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6,3，5，4，6}，求背包问题的最大装包价值。若此为0-1背包问题，分析该问题具有最优子结构，定义递归式为其中c(i，j)表示i个物品、容量为j的0-1背包问题的最大装包价值，最终要求解c(n,W)。 采用自底向上的动态规划方法求解，得到最大装包价值为(62)，算法的时间复杂度为(63)。 若此为部分背包问题，首先采用归并排序算法，根据物品的单位重量价值从大到小排序，然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量，则得到的最大装包价值为(64)，算法的时间复杂度为(65)。A.11B.14C.15D.16.67 ” 相关考题
考题
●试题四阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【程序4．1说明】"背包问题"的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，w2，．．．，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。如下程序均能求得"背包问题"的一组解，其中程序4．1是"背包问题"的递归解法，而程序4．2是"背包问题"的非递归解法。【程序4．1】#includestdio．h#define N 7#define S 15int w［N+1］={0，1，4，3，4，5，2，7}；int knap(int s，int n){ if(s==0)return 1；if (s0||(s0 n1))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】#includestdio．h#define N 7#define S 15typedef 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.s0 || x．n =0)rep=0；else{x．s= (4) ；x．job=1；(5) =x；}}if(!k){rep=1；while(top=1rep){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；}
考题
阅读下列程序说明和C++代码，将应填入(n)处。【说明】“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1；w2，……，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。如下程序均能求得“背包问题”的一组解，其中程序4.1是“背包问题”的递归解法，而程序4.2是“背包问题”的非递归解法。【程序4.1】include＜stdio.h＞define N 7define S 15int 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 7define S 15typedef 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＞＝1rep){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；}
考题
阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。【说明】“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，w2，…，wn。希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。如下程序均能求得“背包问题”的一组解，其中程序1是“背包问题”的递归解法，而程序2是“背包问题”的非递归解法。【程序1】include＜stdio.h＞define N 7define S 15int 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 7define S 15typedef 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
考题
阅读下列函数说明和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 255struct 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)处。
考题
阅读下列说明，回答问题1至问题2，将解答填入答题纸的对应栏内。【说明】0—1背包问题可以描述为：有n个物品，对i=l，2，…，n，第i个物品价值为vi，重量为wi(vi和wi为非负数)，背包容量为w(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即，其中，xi∈{O，1}，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。用回溯法求解此0—1背包问题，请填充下面伪代码中(1)～(4)处空缺。回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOuND(v，w，k，W)函数，其中v、w、k和w分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。下面给出0—1背包问题的回溯算法伪代码。函数参数说明如下：w：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。变量说明如下：cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。BKNAP(W，n，w，v，fw，fp，X)1 cw←cp02 (1)3 fp←l4 while true5 while k≤n and cw+w[k]≤w d。6 (2)7 cp←cp+v[k]8 Y[k]←l9 k←k+110 if kn then11 if fpcp then12 fp←cp13 fw←cw14 k←n15 X←Y16 else Y (k)←O17 while BOUND(cp，cw，k，W) ≤fp do18 while k≠O and Y(k)≠l d019 (3)20 if k=0 then return2l Y[k]←022 cw←cw-w[k]23 cp←cp-v[k]24 (4)
考题
阅读以下程序说明和C程序，将程序段中(1)～(7)空缺处的语句填写完整。【说明】【C程序1】用回溯算法来产生由0或1组成的2m个二进位串，使该串满足以下要求。视串为首尾相连的环，则由m位二进制数字组成的2m个子序列，每个可能的子序列都互不相同。例如，如果m=3，在串11101000首尾相连构成的环中，由3位二进制数字组成的每个可能的子序列都在环中恰好出现一次，它们依次是111，110，101，010，100，000，001，011，如图2-14所示。【C程序2】是求“背包问题”的一组解的递归算法程序。“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为W1，W2，…，Wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。【C程序1】define N 1024define M 10int b [N+M-1]int equal(int k, int j int m) {int i;for(i=0; i＜m; i++if ( b[ k + i] (1) )return 0;return 1; }int exchange (int k, int m, int v){while ( b[ k + m - 1 ) == v ) {b[ kncm--i]=! v (2);}(3)=v;return k;}init ( iht v) {int kfor( k = 0;K = N + M - 1;k++)b[k] = v;}main ( ) {int m, v, k, n, j;printf ('Enter m (l＜m＜10) , v v=0, v=1)\ n") ;scanf (" %d%d , m, v);n = 0x01 ＜＜ m;init (!v);k=0;while((4)＜ n)for (j=0;j＜k;j++)if (equal (k, j, m)) {k=exchange (k, m, v)j=(5);}for (k= 0 ;k＜n ;k++ )print{ (" %d\ n" , b[k]) ;}}【C程序2】include＜stdio. h＞define N 7define S 15int 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 ((6))) {printf( "4d", w[n]);return 1;}return (7)}main ( ) {if (knap (S, N)printf("OK:\n");elseprintf("NO!\n")}
考题
*部分背包问题可有贪心法求解：计算Pi/Wi数据结构：w[i]:第i个背包的重量；p[i]:第i个背包的价值；1．0-1背包： 每个背包只能使用一次或有限次(可转化为一次)：A.求最多可放入的重量。
考题
利用贪心法求解0/1背包问题时，(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时，将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X)，设fi(x)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为 wj和pj(j=1～n)。则依次求解f0(x)、f1(x)、...、fn(X)的过程中使用的递推关系式为(56)。.A．优先选取重量最小的物品B．优先选取效益最大的物品C．优先选取单位重量效益最大的物品D．没有任何准则
考题
0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi ，重量为wi（vi，和wi为非负数），背包容量为W（W为非负数），选择其中一些物品装入背包，使装入背包物品的总价值最大，，且总重量不超过背包容量，即，其中，xi∈{0,1}，xi=0表示第i个物品不放入背包，xi=1表示第i个物品 放入背包。【问题1】（8分）用回溯法求解此0-1背包问题，请填充下面伪代码中（1）~（4）处空缺。回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND（v,w,k,W）函数，其中v, w, k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。下面给出0-1背包问题的回溯算法伪代码。函数参数说明如下：W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。变量说明如下：cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。BKNAP(W,n,w,v,fw,fp,X）1 cw ← cp ← 02 （1）3 fp ← -14 while true5 while k≤n and cw＋w[k]≤W do6 （2）7 cp ← cp＋v[k]8 Y[k]← 19 k ← k+110 if k＞n then11 if fp＜cp then12 fp ← cp13 fw ← ew14 k ← n15 X ← Y16 else Y(k)← 017 while BOUND(cp,cw,k,W) ≤fp do18 while k≠0 and Y(k)≠1 do19 （3）20 if k＝0 then return21 Y[k]←022 cw ← cw ← w[k]23 cp ← cp ← v[k]24 （4）
考题
利用贪心法求解0/1背包问题时，(26)能够确保获得最优解。用动态规划方求解O/1背包问题时，将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1，i，X)设fi(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为W和p(j=1～n)，则依次求解f0(X)，f1(X)，…，fn(X)的过程中使用的递推关系式为(27)。A．优先选取重量最小的物品B．优先选取效益最大的物品C．优先选取单位重量效益最大的物品D．没有任何准则
考题
【问题 1】（8 分）用回溯法求解此 0-1 背包问题，请填充下面伪代码中（1）～（4）处空缺。回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND( v,w,k,W )函数，其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。下面给出 0-1背包问题的回溯算法伪代码。函数参数说明如下:W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。变量说明如下：cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。
考题
考虑下述背包问题的实例。有5件物品，背包容量为100,每件物品的价值和重量如下表所示，并已经按照物品的单位重量价值从大到小徘好序，根据物品单位重量价值大优先的策略装入背包中，则采用了（请作答此空）设计策略。考虑0/1背包问题（每件物品或者全部放入或者全部不装入背包）和部分背包问题（物品可以部分装入背包），求解该实例，得到的最大价值分别为（ ）。
A.分治
B.贪心
C.动态规划
D.回溯
考题
考虑下述背包问题的实例。有5件物品，背包容量为100,每件物品的价值和重量如下表所示，并已经按照物品的单位重量价值从大到小徘好序，根据物品单位重量价值大优先的策略装入背包中，则采用了（ ）设计策略。考虑0/1背包问题（每件物品或者全部放入或者全部不装入背包）和部分背包问题（物品可以部分装入背包），求解该实例，得到的最大价值分别为（请作答此空）。
A.605和630
B.605和605
C.430和630
D.630和430
考题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】0-1背包问题定义为:给定1个物品的价值v[1....i]、重量w[1....i]和背包容量T,每个物品装到背包里或者不装到背包里,求最优的装包方案,使得所得到的价值最大。0-1背创问题具有最优子结构性质,定义c为最优装包方案所获得的最大价值则可得到如下所示的递归式。
【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)。
考题
有0-1背包问题如下： n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），单位重量物品价值（7.5，2.67，1.5，0.8，0.375，0.1）
考题
考虑背包问题：n=6，物品重量W=（1，5，2，3，6，1），价值P=（15，59，21，30，60，5），背包载重量C＝10。能放进背包的物品价值最大为（）。A、101B、110C、115D、120
考题
对于如下描述的背包问题，请计算最终装入背包的最大价值和以及各个物品装入背包的数量。 背包容量：C＝50千克。3件物品。物品1重20千克，价值100元；物品2重20千克，价值120元；物品3重30千克，价值90元。
考题
有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？
考题
举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
考题
问答题举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
考题
问答题有0-1背包问题如下： n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），单位重量物品价值（7.5，2.67，1.5，0.8，0.375，0.1）
考题
问答题有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？
考题
问答题对于如下描述的背包问题，请计算最终装入背包的最大价值和以及各个物品装入背包的数量。 背包容量：C＝50千克。3件物品。物品1重20千克，价值100元；物品2重20千克，价值120元；物品3重30千克，价值90元。
考题
问答题在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明算法的正确性）
热门标签
最新试卷