动态规划--C#求解01背包

2021-01-12 14:52发布

背包问题(Knapsack problem)是一种组合优化的NP完全问题。

给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。

应用: 
背包问题出现在各种领域的现实世界的决策过程中,例如寻找最少浪费的方式来削减原材料, 选择投资和投资组合,选择资产支持资产证券化 ,和生成密钥为Merkle-Hellman 和其他背包密码系统

1,穷举法(把所有情况列出来,比较得到 总价值最大的情况): 
求解思路:先不想其他的,求最高价格,那么对于每种物体来说,都有两种状态,要么装进背包,要么不装,有n种物品,就会是n的2次方种,装背包的方式,(如果容量增大,物品增多,这个方法的运行时间将成指数增长),我用二进制的01的形式表示物品是否在背包中,代码如下:

using System;


namespace _4_2_1动态规划_01背包_穷举

{

    class Program

    {

        static void Main(string[] args)

        {          

            //包的最大容纳量

;           int m = 10;


            //物品重量

            int[] weight = {0, 3, 4, 5 };

            //和上面所对应物品的价值

            int[] value = { 0, 4, 5, 6 };


//输出的结果是11       

     Console.WriteLine(Exhausttiity(m,weight,value));



            Console.ReadKey();

        }


        public static int  Exhausttiity(int m,int[] w,int[] p)

        {

            int num = w.Length - 1;    //物品的个数

            int maxPrice = 0;      //物品最大价值


            for (int i = 0; i < Math.Pow(2,m); i++)

            {

                //取得i上第一个位置上的二进制值

                int weihght = 0;

                int price = 0;

                for (int j = 1; j <= num; j++)

                {

                    int result = Get2(i, j);

                    if(result == 1)

                    {

                        weihght += w[j];

                        price += p[j];

                    }

                }

                if(weihght <= m && price > maxPrice)

                {

                    maxPrice = price;

                }

            }

            return maxPrice;

        }


        //取得i上number位 上的二进制值,是1还是0

        public  static int Get2(int i,int number)

        {

            int A = i;

            int B = (int)Math.Pow(2, number - 1);

            //二进制的与运算

            int result = A & B;

            if (result == 0)

            {

                return 0;

            }else{

                return 1;

            }          

        }

    }

}

动态规划算法 
我们要求得i个物体放入容量为m(kg)的背包的最大价值(记为 c[i,m])。在选择物品的时候,对于每种物品i只有两种选择,即装入背包或不装入背包。某种物品不能装入多次(可以认为每种物品只有一个),因此该问题被称为0-1背包问题 
对于c[i,m]有下面几种情况:

  1. c[i,0]=c[0,m]=0

  2. 当w[i]>m 时 c[i,m]=c[i-1,m] 最后一个物品的重量大于容量,直接舍弃不用)

  3. 当w[i]<=m的时候有两种情况,一种是放入i,一种是不放入i 
    a, 不放入i c[i,m]=c[i-1,m] 
    b, 放入i c[i,m]=c[i-1,m-w[i]]+p[i] 
    上面a,b做比较,取得较大的值记录: c[i,m]=max(不放入i,放入i)

递归解决01背包:

using System;


namespace _4_2_3动态规划_01背包_递归优化

{

    class Program

    {

        //11 是 最大可拿的方案有12种,4 是 最大可拿物品的个数

        public static int[,] result = new int[11,4];

        static void Main(string[] args)

        {

            //包的最大容纳量

            int m = 10;

            //物品重量

            int[] weight = { 0, 3, 4, 5 };

            //和上面所对应物品的价值

            int[] value = { 0, 4, 5, 6 };


            Console.WriteLine(UpDown(m, 3, weight, value));


            Console.ReadKey();

        }


        //m是背包容量,i是物品个数,wp是物品的重量和价值数组

        public static int UpDown(int m, int i, int[] w, int[] p)

        {

            //物品个数为0或者背包容量为0时,最大利润为0

            if (i == 0 || m == 0) { return 0; }


            //若不为0则表示求解过

            if (result[m,i] != 0)

            {

                return result[m, i];

            }


            if (w[i] > m)

            {

                result[m,i] = UpDown(m, i - 1, w, p);

                return result[m, i];

            }

            else

            {

                int maxValue1 = UpDown(m - w[i], i - 1, w, p) + p[i];

                int maxValue2 = UpDown(m, i - 1, w, p);

                if (maxValue1 > maxValue2)

                {

                    result[m, i] = maxValue1;

                }

                else

                {

                    result[m, i] = maxValue2;

                }

                return  result[m, i]; 

            }

        }


    }

}




作者:Czhenya

链接:https://czhenya.blog.csdn.net/article/details/78947950

来源:CSDN
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。