C#笔记：动态规划算法
一个复杂的问题，通常逐级会分解成一系列小问题。而且很多情况下，某些小问题是相似的。但是使用传统的递归，会将相同相似的小问题进行重复的计算。这样浪费了算力。 所谓动态规划算法，实质是使用一个表，记录下所有小问题的值。如果在计算中再次遇到相同问题，则直接取值。不做计算。显然，如果每个小问题都是不同的，那么此算法没有优势。 比如斐波那契数列，就是一个简单的例子。 定义：
Fab(n)= Fab(n-1)+Fab(n-2)
Fab(1)=Fab(2)=1;实现1：
static int GetFab(int n)
{
if (n == 1) return 1;
if (n == 2) return 1;
return GetFab(n - 1) + GetFab(n - 2);
}假如我们求Fab(5) 。那我们需要求Fab（4） +Fab（3）。 Fab(4)=Fab(3)+Fab(2).....显然。 Fab（3）被计算机不加区别的计算了两次。而且随着数字的增大，计算量是指数增长的。 如果我们使用一个数组，记录下Fab的值。当Fab(n)!=null 时。直接读取。那么，我们就能把时间复杂度控制在 n 以内。 实现2：
static int[] fab = new int[6];
static int GetFabDynamic(int n)
{
if (n == 1) return fab[1] = 1;
if (n == 2) return fab[2] = 1;
if (fab[n] != 0)//如果存在，就直接返回。
{
return fab[n];
}
else //如果不存在，就进入递归，并且记录下求得的值。
{
return fab[n] = GetFabDynamic(n - 1) + GetFabDynamic(n - 2);
}
}这就是，动态规划算法的 备忘录模式。只需要把原来的递归稍微修改就行了。 下面是0-1背包问题的解法。可以对比一下。（一个限重w的背包，有许多件物品。sizes[n]保存他们的重量。values[n]保存它们的价值。求不超重的情况下背包能装的最大价值）
static int[] size = new int[] { 3, 4, 7, 8, 9 };// 5件物品每件大小分别为3, 4, 7, 8, 9 且是不可分割的 0-1 背包问题
static int[] values = new int[] { 4, 5, 10, 11, 13 };//// 5件物品每件的价值分别为4, 5, 10, 11, 13
static int capacity = 16;
static int[,] dp = new int[6, capacity + 1];
static int knapsack(int n, int w)
{
if (w < 0) return -10000;
if (n == 0) return 0;
if (dp[n, w] != 0)
{
return dp[n, w];
}
else
{
return dp[n, w] = Math.Max(knapsack(n - 1, w), knapsack(n - 1, w - size[n - 1]) + values[n - 1]);
/*
* knapsack(n,w) 指在前N件物品在W剩余容量下的最大价值。
* 这个公式的意思是，对于某一件物品，
* 1、如果选择装进去，那么，当前价值=前面的n-1件物品在空位w - size(n)下的最大价值（因为空位需要留出，空位也隐含了价值）。
* 再加上这件物品的价值。等于 knapsack(n - 1, w - size[n - 1]) + values[n - 1]
* 2、 如果我们选择不装进去，那么，在n-1物品的情况下空位仍然在，当前价值 = 前面n-1件物品在空位w下的最大价值。
* 等于knapsack(n - 1, w)
* 注意：随着演算，某一情况下的价值不会一成不变。
* 此时我们做出决策：到底是在装入时的价值大，还是不装入时的价值大呢？我们选择上面两种情况中值较大的。并记录在案。
* 最后dp[N,M]就是我们要求的值。
*/ }
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-02-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读