2. 计算机
  3. 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 0-1背包问题定义为：给定i个物品的价值v[1…i]、重量w[1…i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 0-1背包问题定义为：给定i个物品的价值v[1…i]、重量w[1…i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。

admin2021-03-24  109
问题 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
    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程序

    #include＜Stdio．h＞
    #include＜math．h＞
    #define N 6
    #define maxT 1000
    int c[N][maxT]={0}；

    intMemoized_Knapsack(int V[N]，int w[N]，intT){
        inti；
        int j；
        for(i=0；i＜N；i++){
            for(j=0；j＜=T；j++){
                c[j]=一1；
            }
        }
        returnCalculate_Max_Value(v，w，N-1，T)；
    }
    intcalculate_Max_Value(int v[N]，  int w[N]，inti，int j){
        int temp=0；
        if(c[j]!=一1){
            return  (1)  ；
        }
        if(i=0 || j==0){
            c[j]=0；
        }else{
            c[j]=Calculate_Max_Value(v，w，i-1，j)；
            if(  (2)  ){
                temp=  (3)  ；
                if(c[j]＜temp){
                      (4)  ；
                }
            }
        }
        return c[j]；
    }
根据说明和C代码，填充C代码中的空(1)～(4)。
选项
答案(1)c[i][j] (2)w[i]＜=j (3)Calculate_Max_Value(v，w，i-1 j-w[i])+v[i] (4)c[i][j]=temp
解析 一般情况下，采用动态规划法求解最优化问题是构建递归式，然后自底向上迭代地求解。这里采用了自顶向下的递归求解方法，但是和传统的递归又不同。在求解问题的过程中，对第一次遇到的问题采用递归方法求解，把解存放到数组中，后面再次遇到该问题时，直接到数组中查询。
    C程序中已经说明c[j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值。开始时c[j]初始化为一1。calculate_Max_Value函数用来计算c[j]的值。进入函数后，先判断c的值是否为-1，如果不是，说明己经计算过，直接返回该值即可，因此空(1)填c[j]；如果是-1，那么需要递归计算。空(2)上面的语句计算了在前i-1项，容量为j的背包问题值的最大价值，因此空(2)填入w＜=j，考虑在前i-1项，容量为j-w的背包问题值的最大价值，比较两者的大小关系，因此空(3)和空(4)分别填入Calculate_Max_Value(v，w，i-1 j-w)+v和cD]=temp。
转载请注明原文地址:https://kaotiyun.com/show/LoxZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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