C# 0-1背包问题

0-1背包问题属于动态规划范畴。什么是动态规划？就是当前问题的解依赖于子问题的最优解。

个人认为对于0-1背包解释较好的博文：https://www.cnblogs.com/strick/p/13403324.html

本文只给出C#代码实现。

 class goods
    {
        public int weight;
        public int value;
        public goods(int w,int v)
        {
            weight = w;
            value = v;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            // 0-1 背包问题
            List<goods> list = new List<goods>();
            list.Add(new goods(0, 0));
            list.Add(new goods(1,1500));
            list.Add(new goods(4, 3000));
            list.Add(new goods(3, 2000));
            list.Add(new goods(2, 1000));

            int capacity = 21;  // 实际容量+1

            int[,] result = new int[list.Count, capacity];

            for(int i = 1;i < capacity;i++)
            {
                result[1, i] = list[1].value;
            }

            for(int i = 2;i < list.Count;i++)
            {
                for(int j = 1;j < capacity;j++)
                {
                    if(list[i].weight <= j && j - list[i].weight >= 0)   // 首先要保证当前容量能够容下该物品
                    {
                        result[i, j] = Math.Max(list[i].value + result[i-1,j - list[i].weight], result[i - 1, j]);    // 状态转移方程
                    }else
                    {
                        result[i, j] = result[i - 1, j];
                    }
                }
            }


　　　　　　　　// 输出
            for (int i = 0; i < list.Count; i++)
            {
                for (int j = 0; j < capacity; j++)
                {
                    if (i == 0) { Console.Write(j + "   ");continue; } ;
                    if (j == 0) { Console.Write(i + " ");continue; }
                    Console.Write(result[i,j] + ",");
                }               
                Console.Write('
');
            }
            Console.ReadLine();
        }
    }