网站建设合作合同,标志设计英文,站长工具seo综合查询源码,网站建设谢辞动态规划 动态规划--0-1背包问题穷举法#xff08;把所有情况列出来#xff0c;比较得到总价值最大的情况#xff09;动态规划算法01背包问题递归实现#xff08;不带备忘录的自顶向下法#xff09;01背包问题-递归实现#xff08;带备忘的自顶向下法#xff09;01背包问… 动态规划 动态规划--0-1背包问题穷举法把所有情况列出来比较得到总价值最大的情况动态规划算法01背包问题递归实现不带备忘录的自顶向下法01背包问题-递归实现带备忘的自顶向下法01背包问题自底向上法 动态规划–0-1背包问题
问题描述 假设现有容量m kg的背包另外有 i 个物品重量分别为w[1] w[2]…w[i] (kg)价值分别为p[1]、p[2]…p[i] (元)将哪些物品放入背包可以使得背包的总价值最大最大价值是多少 (示例一m10 i3重量和价值分别为3kg-4元4kg-5元 5kg-6元)
穷举法把所有情况列出来比较得到总价值最大的情况
如果容景增大物品增多这个方法的运行时间将成指数增长每一个物品都有两种状态放与不放0和1状态所以如果有n个物品就有2的n次方种情况
internal class Program
{static void Main(string[] args){int m;int[] w { 0, 3, 4, 5 };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));}public static int Exhaustivity(int m, int[] w,int[] p){int i w.Length - 1;//物品的个数int maxPrice 0;for(int j 0; j Math.Pow(2,m); j){//取得j 上某一个位的二进制值int weightTotal 0;int priceTotal 0;for(int number 1; number i; number){int result Get2(j, number);if (result 1){weightTotal w[number];priceTotal p[number];}}if(weightTotal m priceTotal maxPrice){maxPrice priceTotal;}}return maxPrice;}public static int Get2(int j, int number){int A j;int B (int)Math.Pow(2,number - 1);int result A B;if(result 0){return 0;}return 1;}
}动态规划算法
我们要求得 i 个物体放入容量为m(kg)的背包的最大价值记为c[i,m])。在选择物品的时候对于每种物品只有两种选择即装入背包或不装入背包。某种物品不能装入多次可以认为每种物品只有一个因此该问题被称为0-1背包问题
对于c[i,m]有下面几种情况
c[i,0]c[0,m]0当w[i]m时 c[i,m]c[i-1,m] (最后一个物品的重量大于容量直接舍弃不用)当w[i]m的时候有两种情况一种是放入i,一种是不放入i 不放入ic[i,m]c[i-1,m]放入i c[i,m]c[i-1,m-w[i]p[i]c[i,m]max(不放入i,放入i)
01背包问题递归实现不带备忘录的自顶向下法
internal class Program
{static void Main(string[] args){int m;int[] w { 0, 3, 4, 5 };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));}//m是背包容量//i是物品个数//wp是物品的重量和价值的数组public static int UpDown(int m, int i,int[] w, int[] p ) //返回值是m可以存储的最大价值{if (i 0||m 0){return 0;}if (w[i] m){return UpDown(m,i-1,w, p );}else{int maxValue1 UpDown(m - w[i], i - 1, w, p ) p[i];int maxValue2 UpDown(m, i - 1, w, p );if (maxValue1 maxValue2){return maxValue1;}return maxValue2;}}
}01背包问题-递归实现带备忘的自顶向下法
internal class Program
{public static int[,] result new int[11, 4];static void Main(string[] args){int m;int[] w { 0, 3, 4, 5 };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));}//m是背包容量//i是物品个数//wp是物品的重量和价值的数组public static int UpDown(int m, int i, int[] w, int[] p) //返回值是m可以存储的最大价值{if (i 0 || m 0){return 0;}if (result[m,i]!0){return result[m,i];}if (w[i] m){result[m,i] UpDown(m, i - 1, w, p);return result[m,i];}else{int maxValue1 UpDown(m - w[i], i - 1, w, p) p[i];int maxValue2 UpDown(m, i - 1, w, p);if (maxValue1 maxValue2){result[m, i] maxValue1;}else{result[m,i] maxValue2;}return result[m,i];}}
}01背包问题自底向上法
internal class Program
{static void Main(string[] args){int m;int[] w { 0, 3, 4, 5 };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));}public static int[,] result new int[11, 4];public 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 m1; tempM){for(int tempI 1; tempI i1;tempI){if (result[tempM,tempI] ! 0 )continue;if (w[tempI] tempM){result[tempM, tempI] result[tempM, tempI - 1];}else{int maxValue1 result[tempM - w[tempI], tempI-1]p[tempI];int maxValue2 result[tempM, tempI - 1];if (maxValue1 maxValue2){result[tempM, tempI] maxValue1;}else{result[tempM,tempI] maxValue2;}}}}return result[m,i];}
}
