01背包问题有三种解法，穷举法，自顶向下的动态规划，自底向上的动态规划。
穷举法，要用到进制转换以及位运算符。
自底向下总result[m,i],相当于质量为m时放第i件物品时的最大价值。 列如result[5,2],就是质量为5，放了前两件物品时的最大价值。
当一个物品进来时有几种情况
如果如果进来的物品 w[i]>m放不下 result[m,i] = result[m,i-1] 放下有两种情况 放入背包，不放入背包 放入 result[m,i]=result[m-w[i],i-1]+p[i] (把该物品放入的话，先把这个物品的价值加上，然后加上不放入这个物品的最大价值) 不放入 result[m,i]=result[m,i-1]相当于这个物品没放 然后比较放和不放的价值。
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 背包问题 { class Program { //备忘录用来保存数据 m i 最大价值 static int[,] arry= new int [200,8]; static int[,] result = new int[200, 8]; static void Main(string[] args) { //int a = 30; //int b = 8; //Console.WriteLine(a & b); //Console.Read(); int m; int[] w = { 0, 10, 40, 30, 50, 35, 40, 30 }; int[] p = { 0, 35, 30, 6, 50, 40, 10, 25 }; Console.WriteLine(Exhaustivity(150, w, p)); Console.WriteLine(UpToDown(150, 7, p, w)); Console.WriteLine(UpToDown2(150, 7, p, w)); Console.WriteLine(BottomUp(150, 7, w, p)); Console.ReadKey(); } /// <summary> /// 穷举法 /// </summary> /// <returns></returns> static int Exhaustivity(int m,int []w,int []p) { int i = w.Length; int totalP = 0; int totalW = m; for (int j =1;j<= Math.Pow(2,i);j++) { int tempP = 0; int tempW = 0; for (int num=1;num<i;num++) { int result = Get2(j, num); if(result==0) { continue; } else { tempP += p[num]; tempW += w[num]; } } if(tempP>totalP&&tempW<=totalW) { totalP = tempP; } } return totalP; } /// <summary> /// 自顶向下不带备忘 /// </summary> /// <param name="m"></param> /// <param name="i"></param> /// <param name="p"></param> /// <param name="w"></param> /// <returns></returns> static int UpToDown(int m,int i,int []p,int []w) { if(m==0||i==0) { return 0; } if (w[i] > m) { return UpToDown(m, i - 1, p, w); } else { ///1不装 2装 int temp1 = UpToDown(m, i - 1, p, w); int temp2 = UpToDown(m - w[i], i - 1, p, w) + p[i]; if (temp1 > temp2) { return temp1; } else { return temp2; } } } static int UpToDown2(int m,int i,int []p,int []w) { if (m == 0 || i == 0) { return 0; } if(arry[m,i]!=0) { return arry[m, i]; } if (w[i] > m) { arry[m, i] = UpToDown2(m, i - 1, p, w); return arry[m, i]; } else { ///1不装 2装 int temp1 = UpToDown2(m, i - 1, p, w); int temp2 = UpToDown2(m - w[i], i - 1, p, w) + p[i]; if (temp1 > temp2) { arry[m, i] = temp1; return arry[m,i]; } else { arry[m, i] = temp2; return arry[m, i]; } } } /// <summary> /// 把j传进来然后判断他的第num位是0还是1 /// </summary> /// <param name="num"></param> /// <param name="n"></param> /// <returns></returns> static int Get2(int j,int num) { int a=j; int b =(int) Math.Pow(2,num-1); int result = a & b; if(result==0) { return 0; } return 1; } 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(w[tempI]>tempM) { result[tempM, tempI] = result[tempM, tempI - 1]; } else { //1不放 2放 int temp1 = result[tempM, tempI - 1]; int temp2 = result[tempM - w[tempI], tempI-1]+p[tempI]; if(temp1>temp2) { result[tempM, tempI] = temp1; // return temp1; } else { result[tempM, tempI] = temp2; // return temp2; } } } } return result[m, i]; } } }