软件设计师教程--动态规划（0-1背包问题）

短命女 2021-09-26 17:14 215阅读 0赞

0-1背包问题

这里有n个物品，第i个物品价值为vi，重量为ωi，其中vi和ωi均为非负数，背包的容量为*W*，*W*为非负数。现在需要考虑如何选择装入背包的问题，使装入背包的物品总结之最大。该问题可以形式化描述如下：

int** KnapsackDP(int n,int W,int*Weights,float*Values){
        int i,w;                                                      /*定义，定义背包将最后的总价值 i 和背包重量 w */
        int**c=(int**)malloc(sizeof(int *)*(n+1));                    /*定义，为二维数组申请空间*/
        for (i = 0 ; i <= n ; i++)                                    /*循环，当 i <= n 时一直循环下去*/
            c[i]=(int*)malloc(sizeof(int)(W+1);                       /*定义，初始化二维数组*/
        for(w = 0;w<=W;w++)                                           /*循环，当重量 w = 0 到 W 时，当单个价值为 0 时*/
            c[0][w]=0;                                                /*定义，总价值c[0][w]为零*/
        for(i=1;i<=n;i++){                                            /*循环，当单个价值 i = 0 到 n 时，当重量为 0 时*/
            c[i][0]=0;                                                /*定义，总价值c[i][w]为零*/
            for(w=1;w<=W;w++){                                        /*循环，当 w = 1 到 W 时*/
                if(Weights[i-1]<=w){                                  /*判断，如果已经进入包中的所有物品的总重量 Weights[i-1] 小于背包的重量 w 时*/
                    if(Values[i-1]+c[i-1][w-Weights[i-1]]>c[i-1][w])  /*判断，已经进入包中的所有物品的总价值Values[i-1]加上准备进入包中物品的价值大于该物品没有进入时的价值*/
                    {
                        c[i][w]=Values[i-1]+c[i-1][w-Weights[i-1]];   /*执行，将已经进入包中的所有物品的总价值Values[i-1]加上准备放入物品的价值然后赋值给新的总价值*/
                    }
                    else{                                             /*或则*/
                         c[i][w]=c[i-1][w];                           /*执行，将没有放该物品之前时包中所有物品的总价值赋值给新的总价值（跟之前的价值一样，不变）*/
                    }
                }
                else                                                  /*或则*/
                    c[i][w]=c[i-1][w];                                /*执行，将没有放该物品之前时包中所有物品的总价值赋值给新的总价值（跟之前的价值一样，不变）*/
                }
            }
           return c;                                                  /*输出，输出总价值c*/
        }