2. 从业资格
  3. 0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1…i]和背包容

0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1…i]和背包容

练习题库2022-08-02  42
问题 0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1…i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。0-1背包问题具有最优子结构性质。定义c[T]为最优装包方案所获得的最大价值，则可得到如下所示的递归式。【c代码】下面是算法的C语言实现。（1）常量和变量说明T:背包容量v[]:价值数组w[]:重量数组c[][]:c[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[j]
（2）i>0&&j>=w
（3）Calculate_Max_Value(v,w,i-1,j-w)+v
（4）c[j]=temp
【问题2】
（5）动态规划
（6）自顶向下
【问题3】
（7）40
本题考查的是动态规划法，将中间结果存在二维数组c[][]当中。
【问题1】
结合题干描述中的递归式，函数最终返回值应该是c[T]，又根据代码上下文，T在函数中传参为j，所以第（1）空返回的结果为c[j]。
根据递归式和代码上下文可知，c[j]=0已处理，if后面处理的是max递归部分，又根据上下文可以看到temp会与c[j]进行比较，递归时i=i-1，所以这里判断的是temp与c[i-1][T]的值，第（3）空的处理是将c[i-1][j-w]+v传递给temp，即temp=Calculate_Max_Value(v,w,i-1,j-w)+v，注意这里不是直接穿c[][]数组值，而是递归调用Calculate_Max_Value()函数。那么第（2）空缺失的判断条件根据第3个表达式条件为i>0且T>=w，对应代码中的参数即i>0&&j>=w。
第（4）空是c[j]＜temp比较后的返回值，根据题干，我们需要返回max最大值，最终返回的结果是c[j]，因此要保证c[j]最大，当c[j]＜temp时，将temp赋值给c[j]，即c[j]=temp。
【问题2】
本题采用递归形式，并且求取的是全局最优解，中间结果存在二维数组c[][]当中，所以采用的是动态规划法。动态规划法采用递归形式，i会从N-1递减至0，所以是自顶向下的方式。
【问题3】
本题考查最优解，可以忽略题干描述，直接凑数，可得第3和第4个物品，重量为11，价值为40，此时为最优解，即为最大价值。
转载请注明原文地址:https://tihaiku.com/congyezige/2409598.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)