01背包问题 C#解法

01背包问题

假设现有容量m的背包，有i个物品，重量分别为w[1],w[2]…w[i]，价值分别为p[1],p[2]…p[i]，将哪些物品放入背包可以使得背包的总价值最大？最大价值是多少？ （示例1：m=10，i=3，物品重量-价值：3-4 , 4-5 , 5-6）

第一种 不带备忘的自顶向下法

using System; namespace CSharp { 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));//容量10，物品3 Console.ReadKey(); } public static int UpDown(int m, int i, int[] w, int[] p) { 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; } } } }

思路：对于最大价值，有四种情况： 1.当i或m为0时，此时背包容量为0或者物品个数为0，直接返回0。 2.当最后一个物品的重量超出容量，舍弃不用。返回i-1时的情况。 3.当最后一个物品的重量小于容量，可以装下但不放入时（小于最大价值），直接返回i-1时的情况。 4.当最后一个物品的重量小于容量，可以装下且放入时，记录此时价值并和之前作比较，返回较大的那一个。

递归解法，时空复杂度极高，效率低下。

第二种 动态规划

using System; namespace CSharp { class Program { static int[,] result = new int[11, 4]; static void Main(string[] args) { int[] w = { 0, 3, 4, 5 };//物品重量 int[] p = { 0, 4, 5, 6 };//物品价值 Console.WriteLine(BottomUp(10, 3, w, p));//容量10，物品3 Console.ReadKey(); } public static int BottomUp(int m, int i, int[] w, int[] p) { if (result[m, i] != 0) return result[m, i]; for (int M = 1; M < 11; M++) { for (int I = 1; I < 4; I++) { if (result[M, I] != 0) continue; if (w[I] > M) result[M, I] = result[M, I - 1]; else { int maxValue1 = result[M - w[I], I - 1] + p[I]; int maxValue2 = result[M, I - 1]; if (maxValue1 > maxValue2) result[M, I] = maxValue1; else result[M, I] = maxValue2; } } } return result[m, i]; } } }

思路：和前一个思路大致相同，唯一不同的是用一个数组来承接每次放入物品的价值，之后再次调用则不需要重新计算，直接取数组中的值即可。