信管网案例分析

阅读下列说明和C代码，回答问题1至问题3。

【说明】

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

【问题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)。

信管网参考答案：

【问题1】

(1)c[i][j]

(2)i>0&&j>=w[i]

(3)calculate_max_value(v,w,i-1,j-w[i])+v[i]

(4)c[i][j]=temp

【问题2】

(5)动态规划

(6)自顶向下

【问题3】

(7)40

查看解析：www.cnitpm.com/st/4177310833.html

相关推荐：

点击查看/下载：软件设计师历年真题汇总

点击查看：软件设计师在线培训课程 丨 免费试听课程

免费练习：软件设计师考试题库(模拟试题、章节练习、每日一练)