答案及解析：[问答题]0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1…i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。0-1背包问题具有最优子结构性质。定义

问题：

[问答题] 0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1…i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。0-1背包问题具有最优子结构性质。定义c[i][T]为最优装包方案所获得的最大价值，则可得到如下所示的递归式。中级软件设计师,历年真题,2019年下半年（下午）《软件设计师》真题

【c代码】下面是算法的C语言实现。（1）常量和变量说明T:背包容量v[]:价值数组w[]:重量数组c[][]:c[i][j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值（2）C程序中级软件设计师,历年真题,2019年下半年（下午）《软件设计师》真题

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

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题