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

admin2021-03-24  53

问题 阅读下列说明和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)