练题-软考真题

软考真题

第4题

【说明】

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程序

本人将不方便阅读的图片梳理成文字


#include 
#include 
#define N6
#define maxT 1000
int c[N][maxT]= {
	0
}
;
int Memoized_Knapsack(int v[N],int w[N],int T) {
	int i;
	int j;
	for (i=0; i
	for (j=0; j<=T; j++) {
		c[i][f]= -1;
	}
}
return Calculate_Max_Value(v, w, N-1, T);
}
int Calculate_Max_Value(int v[N],int w[N], int i, int j) {
int temp =0;
if (c[i][j]!=-1) {
	(1)
}
if (i==0||j==0) {
	c[i][j]=0;
} else {
	c[i][j]=Calculate_Max_Value(v, w, i-1, j);
	if( (2) ) {
		temp=(3) ;
		if(c[i][j]
		(4)
	}
}
}
return c [i][j];
}

问题：4.1
(8分)
根据说明和C代码，填充C代码中的空(1) ~ (4)。

问题：4.2
(4分)
根据说明和C代码，算法采用了 (5) 设计策略。在求解过程中，采用了(6)
(自底向上或者自顶向下)的方式。

问题：4.3
(3分)
若5项物品的价值数组和重量数组分别为v[]= {0,1,6,18,22,28}和w[]= {0,1,2,5,6,7}背包容量为T= 11,则获得的最大价值为 (7) 。

2019��

正确答案：

你的答案：

上一题

下一题

请先在App中激活(应用市场搜“软考真题”)

知识点：

试卷：

2019年下半年下午试卷案例