一.动态规划算法
简单理解：在一些分治算法解决的问题中，需要将较大规模的问题转化为较小规模的问题，往往会用到递归。但是在一些问题中，递归的小问题被多次重复运算，浪费了性能，因此可以使用数组或者其他合适的方式将运算过的小规模问题的结果记录下来，再运算小规模的问题时先看是不是已经运算过了，没有运算过再去运算并将结果保存，所以一般分治算法都是从大规模问题开始递归运算，不断将问题规模变小，而动态规划算法则一般从小规模问题开始运算，每次运算分解出的小规模问题都是已经运算过的。如此便使用了存储空间换取了运算时间，减小了时间复杂度。
二.01背包问题
1.穷举法
可以先不考虑背包，考虑被拿走的物品的所有组合情况，n个物品有2n种拿法（每个物品都可以选择拿或者不拿），然后再判断每一种拿法是否能放入背包，能放入背包的情况下计算总价值并比较出最大价值。
static void Main(string[] args) { //记录重量的数组，物品有3种重量，分别是3、4、5 int[] w = { 0, 3, 4, 5 }; //记录物品价值的数组，和重量数组对应，物品价值分别是4、5、6 int[] p = { 0, 4, 5, 6 }; //调用Exhaustivity函数得到7kg的背包放置物品的最大价值 Console.WriteLine(Exhaustivity(9 , w, p)); Console.ReadKey(); } /// <summary> /// 计算给定的mkg背包放置物品的最大价值 /// </summary> /// <param>给定的物品重量</param> /// <param>记录所有物品重量的数组</param> /// <param>记录所有物品对应价格的数组</param> /// <returns>背包中放置物品的最大价值</returns> public static int Exhaustivity(int m,int[] w,int[] p) { //记录放入物品的最大的价格 int maxPrice = 0; //有3个物品，外层就循环2的3次方，即i值从0取到7，i的二进制数字最多3位，每一个i的取值的二进制数字都对应3个物品是否放入背包 //如i为6，二进制为110，代表取前两个物品，不取第3个物品 //又如i为0，二进制为000，代表3个物品均不取；i为1，二进制001，代表只取第3个物品 //通过这种方式穷举所有物品放入背包的情况，然后判断每一种情况重量是否满足要求，再比较价格 for(int i = 0;i < Math.Pow(2,w.Length - 1); i++) { //记录所有被放入背包物品的总重量 int weightTotal = 0; //记录所有被放入背包物品的总价格 int priceTotal = 0; //内层循环负责计算并比较所有物品的总重量和总价格 //内层循环的次数就是物品个数，然后分别判断当前情况下每个物品是否放入背包，j代表第几个物品 for(int j = 1;j <= w.Length - 1; j++) { //计算当前物品是否放入背包 int result = Get2(i, j); //在放入背包的情况下，将重量和价格累加到总重量和总价格上 if(result == 1) { weightTotal += w[j]; priceTotal += p[j]; } } //判断是否超重，不超重的情况下判断价格是不是大于最大价格，如果是更新最大价格 if (weightTotal <= m && priceTotal > maxPrice) maxPrice = priceTotal; } //返回最大价格 return maxPrice; } /// <summary> /// 通过按位与运算得到给定物品number在给定放入情况i中是否放入背包 /// </summary> /// <param>给定的物品放入情况</param> /// <param>给定的物品编号</param> /// <returns></returns> 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; return 1; }