背包问题(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
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。