1.动态规划
什么是动态规划，我们要如何描述它?动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。
动态规划和分治法相似，都是通过组合子问题的解来求解原问题。分治法将问题划分成互不相交的子问题，递归求解子问题，再将他们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做出许多不必要的工作，它会反复的求解那些公共子问题。而动态规划算法对每个子子问题只求解一次，将结果保存到表格中，从而无需每次求解一个子子问题都要重新计算。
2.01背包问题
问题描述：假设现有容量 mkg 的背包，另外有 i 个物品，重量分别为 w[1]w[2] ... w[ i ] （ kg ） , 价值分别为 p[1]p[2] ... p[ i ] （元） , 将哪些物品放入背包可以使得背包的总价值最大？最大价值是多少？
（示例一： m=10 i =3 重量和价值分别为 3kg-4 元 4kg-5 元 5kg-6 元 ）
（1）穷举法（把所有情况列出来，比较得到总价值最大的情况）
如果容量增大，物品增多，这个方法的运行时间将成指数增长
（2）动态规划算法
我们要求得 i 个物体放入容量为 m(kg) 的背包的最大价值（记为 c[ i ， m] ）。在选择物品的时候，对于每种物品 i 只有两种选择，即装入背包或不装入背包。某种物品不能装入多次（可以认为每种物品只有一个），因此该问题被称为 0-1 背包问题
对于 c[ i ， m] 有下面几种情况：
a 、 c[i,0]=c[0,m]=0
b 、 c[ i,m ]=c[i-1,m] w[ i ]>m （最后一个物品的重量大于容量，直接舍弃不用）
w[ i ]<=m 的时候有两种情况，一种是放入 i ，一种是不放入 i
不放入 i c[ i,m ]=c[i-1,m]
放入 i c[ i,m ]=c[i-1,m-w[ i ]]+p[ i ]
c[i,m]=max(不放入i，放入i)
3.代码实现
3.1穷极法
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _509_01背包问题_穷举法
{
class Program
{
static void Main(string[] args)
{
int[] w = { 0, 3, 4, 5 };//每个物品的重量，第1个重3kg,第2个重4kg
int[] p = { 0, 4, 5, 6 };//每个物品对应的价格
Console.WriteLine(Exhaustivity(10, w, p));
Console.WriteLine(Exhaustivity(3, w, p));
Console.WriteLine(Exhaustivity(4, w, p));
Console.WriteLine(Exhaustivity(5, w, p));
Console.WriteLine(Exhaustivity(7, w, p));
Console.ReadKey();
}
/// <summary>
///
/// </summary>
/// <param name="m">背包容量</param>
/// <param name="w">物品重量数组</param>
/// <param name="p">重量对应的价格数组</param>
/// <returns></returns>
private static int Exhaustivity(int m,int[] w,int[] p)
{
int i = w.Length;//物品的个数
int maxPrice = 0;
//每个物品可以放入背包或者不放，也就是每个物品有两种放法
//用0和1表示不放入和放入，有多少个物体就用多少位的二进制表示。
//例如：有4个物品，每一个都不放入即为0 0 0 0，每个都放入即为1 1 1 1
//之间有2的物体个数次方种放法
//（0 0 0 0），（0 0 0 1),(0 0 1 0),(0 1 0 0)......(1 1 1 1)
for(int j=0;j<Math.Pow(2,i);j++)
{
int weigthTotal = 0;
int priceTotal = 0;
//取得j上某一位的二进制值
for(int number=1;number<w.Length;number++)
{
int result= Get2(j, number);
if(result==1)
{
weigthTotal += w[number];
priceTotal += p[number];
}
}
if(priceTotal>maxPrice&&weigthTotal<=m)
{
maxPrice = priceTotal;
}
}
return maxPrice;
}
/// <summary>
/// 取得j的第number位的二进制数是0还是1
/// </summary>
/// <param name="j"></param>
/// <param name="number">二进制数的第number位</param>
/// <returns>返回0或1</returns>
private static int Get2(int j,int number)
{
int A = j;
int B = (int)Math.Pow(2, number - 1);
if ((A & B )== 0) return 0;
return 1;
}
}
}
3.2递归实现
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _510_01背包问题_递归实现_不带备忘的自顶向下法
{
class Program
{
static void Main(string[] args)
{
int[] w = { 0, 3, 4, 5 };//每个物品的重量，第1个重3kg,第2个重4kg
int[] p = { 0, 4, 5, 6 };//每个物品对应的价格
Console.WriteLine(UpDown(10,3, w, p));
Console.WriteLine(UpDown(3, 3, w, p));
Console.WriteLine(UpDown(4, 3, w, p));
Console.WriteLine(UpDown(5, 3, w, p));
Console.WriteLine(UpDown(7, 3, w, p));
Console.ReadKey();
}
/// <summary>
/// 自顶向下的递归实现
/// </summary>
/// <param name="m">背包容量</param>
/// <param name="i">放入物品的个数</param>
/// <param name="w">物品的重量</param>
/// <param name="p">每个物品对应的价格</param>
/// <returns></returns>
private static int UpDown(int m,int i,int[] w,int[] p)
{
if (m == 0 || i == 0) return 0;
if(w[i]>m)//最后一个物品的重量大于背包容量，就不放入背包
{
return UpDown(m, i - 1, w, p);
}
else
{
int priceValue1 = p[i] + UpDown(m - w[i], i - 1, w, p);//放入
int priceValue2 = UpDown(m, i - 1, w, p);//不放入
if(priceValue1>priceValue2)
{
return priceValue1;
}
else
{
return priceValue2;
}
}
}
}
}
3.3带备忘录的自顶向下
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _511_01背包问题_带备忘的自顶向下
{
class Program
{
public static int[,] result = new int[11, 4];//存储已经计算过的
static void Main(string[] args)
{
int[] w = { 0, 3, 4, 5 };//每个物品的重量，第1个重3kg,第2个重4kg
int[] p = { 0, 4, 5, 6 };//每个物品对应的价格
Console.WriteLine(UpDown(10, 3, w, p));
Console.WriteLine(UpDown(3, 3, w, p));
Console.WriteLine(UpDown(4, 3, w, p));
Console.WriteLine(UpDown(5, 3, w, p));
Console.WriteLine(UpDown(7, 3, w, p));
Console.ReadKey();
}
/// <summary>
/// 自顶向下的递归实现
/// </summary>
/// <param name="m">背包容量</param>
/// <param name="i">放入物品的个数</param>
/// <param name="w">物品的重量</param>
/// <param name="p">每个物品对应的价格</param>
/// <returns></returns>
private static int UpDown(int m, int i, int[] w, int[] p)
{
if (m == 0 || i == 0) return 0;
if(result[m,i]!=0)
{
return result[m, i];
}
//else
if (w[i] > m)//最后一个物品的重量大于背包容量，就不放入背包
{
result[m,i]= UpDown(m, i - 1, w, p);
return result[m, i];
}
else
{
int priceValue1 = p[i] + UpDown(m - w[i], i - 1, w, p);//放入
int priceValue2 = UpDown(m, i - 1, w, p);//不放入
if (priceValue1 > priceValue2)
{
result[m,i]= priceValue1;
return result[m, i];
}
else
{
result[m,i]= priceValue2;
return result[m, i];
}
}
}
}
}
3.4自顶向上法-动态规划
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _512_01背包问题_自顶向上法_动态规划
{
class Program
{
static void Main(string[] args)
{
int[] w = { 0, 3, 4, 5 };//每个物品的重量，第1个重3kg,第2个重4kg
int[] p = { 0, 4, 5, 6 };//每个物品对应的价格
Console.WriteLine(BottomUp(10, 3, w, p));
Console.WriteLine(BottomUp(3, 3, w, p));
Console.WriteLine(BottomUp(4, 3, w, p));
Console.WriteLine(BottomUp(5, 3, w, p));
Console.WriteLine(BottomUp(7, 3, w, p));
Console.ReadKey();
}
public static int[,] result=new int[11,4];
private static int BottomUp(int m,int i,int[] w,int[] p)
{
if (result[m, i] != 0) return result[m, i];
for(int tempM=1;tempM<=m;tempM++)
{
for(int tempI=1;tempI<=i;tempI++)
{
if (result[tempM, tempI] != 0) continue;
if(w[tempI]>tempM)//物品重量大于背包容量
{
result[tempM, tempI] = result[tempM, tempI - 1];
}
else
{
int priceValue1 = result[tempM - w[tempI], tempI - 1] + p[tempI];
int priceValue2 = result[tempM, tempI - 1];
if(priceValue1>priceValue2)
{
result[tempM,tempI]= priceValue1;
}
else
{
result[tempM, tempI] = priceValue2;
}
}
}
}
return result[m, i];
}
}
}