动态规划--01背包问题

what？

（1）*解释：（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解成简单的子问题的方式求解复杂问题的方法。

（2）个人理解：把一个大的事情变成小的事情来解决，很像之前的一句古话：大事化小，小事化了！

when？

（1）最优子结构性质。

（2）无后效应。

（3）子问题重叠性质。

how？

那么到底如何用呢？下面以01背包问题为例进行分析！

【分析】

一个小偷去超市偷东西，小偷身带一个容量为17kg的背包，超市比较小，共有5件可偷物品，问：小偷如何偷能使偷得东西价值最大且都能放入背包？

超市中物品的信息如下：

先假设超市可偷物品只有标号1时，背包容量依次为0--17，得到一组数据；

接下来超市可偷物品为2，背包容量依次为0--17；

……

得到如下数表：

【代码实现】

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 自己再写一遍
{
    public class Class1
    {
        static void Main()
        {
            //定义要用到的变量或数组values[]，weights[]，W，w，totval[,],i
            //定义商店中每个物品的重量
            int[] weights = new int[] { 3, 4, 7, 8, 9 };
            //定义商店中每个物品的价值
            int[] values = new int[] { 4, 5, 10, 11, 13 };
            //背包所能承受的总重量
            int W = 17;
            //物品和背包动态的情况
            int i, w;
            //背包中动态的总价值
            int[,] totval = new int[values.Length, W + 1];
            for (i = 0; i <= values.Length - 1; i++)//动态加入物品
            {
                //如果这两个没有=的话会少最后一行数据
                for (w = 0; w <= W; w++)//动态增加背包重量
                {

                    if (w >= weights[i])
                    {
                        if (i > 0)
                        {
                            //这里比的时候是i和i-1比，不是我理解的i-1和i-1比
                            if (totval[i, w] < (totval[i - 1, w - weights[i]] + values[i]))
                            {
                                totval[i, w] = totval[i - 1, w - weights[i]] + values[i];
                            }
                            else
                            {
                                totval[i, w] = totval[i - 1, w];
                            }
                        }

                        else
                        {
                            totval[i, w] = values[i];
                        }

                    }
                    //else
                    //{
                    //    totval[i, w] = totval[i - 1, w];
                    //}


                }



            }
            Console.WriteLine("背包中最大的价值为：" + totval[values.Length - 1, W + 1]);
            //Console.WriteLine("背包中最大的价值为：" + totval[4, W]);
            Console.Read();

        }
    }

}

总结

关于算法，手动去实现一下它的过程还是非常有必要的，这样慢慢让自己站在计算机的角度去思考问题，拥有计算机思维！另外就是写代码，一个自认为特别会的算法，代码未必一次就可以实现，所以要多动手！