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  57
问题 阅读下列说明和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代码，算法采用了  (5)  设计策略。在求解过程中，采用了  (6)  (自底向上或者自顶向下)的方式。
选项
答案(5)动态规划 (6)自顶向下
解析 从题干分析和C代码来看，很容易知道这是一个动态规划算法，算法实现采用的是自顶向下的方法。
转载请注明原文地址:https://kaotiyun.com/show/QoxZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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