贪婪算法、递归计算、动态规划背包问题

怼烎@ 2022-07-14 11:00 162阅读 0赞

//贪婪算法计算背包问题        public static double  ksack(double\[\] values, double\[\] weights, int capacity)        \{            double load = 0;            int i = 0;            double w = 0;            while (load<capacity && i<values.Length)            \{                if (weights\[i\] <= (capacity-load))                \{                    w += values\[i\];                    load += weights\[i\];                \}                else                \{                    double r = (capacity - load) / weights\[i\];                    w += r \* values\[i\];                    load += weights\[i\];                \}                i++;            \}            return w;        \}

//递归计算背包问题
            public static int max(int a, int b)
            {
                return a > b ? a : b;
            }
     
            public static int knapsack(int cappcity, int[] size, int[] value, int n)
            {
                if (n == 0 || cappcity == 0)
                {
                    return 0;
                }
                if (size[n - 1] > cappcity)
                {
                    return knapsack(cappcity, size, value, n - 1);
                }
                else
                {
                    return max(value[n - 1] + knapsack(cappcity - size[n - 1], size, value, n - 1), knapsack(cappcity, size, value, n - 1));
                }
            }

//动态规划背包问题
            public static long dKnapsack(int cappcity, int[] size, int[] value, int n)
            {
                int[,] K = new int[n, cappcity + 1];
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < cappcity; j++)
                    {
                        K[i, j] = 0;
                    }
                }
     
                for (int i = 0; i < n; i++)
                {
                    for (int w = 0; w < cappcity; w++)
                    {
                        if (i == 0 || w == 0)
                        {
                            K[i,w] = 0;
                        }
                        else if (size[i - 1] <= w)
                        {
                            K[i,w] = max(value[i - 1] + K[i - 1,w-size[i-1]], K[i - 1,w]);
                        }
                        else
                        {
                            K[i,w] = K[i - 1,w];
                        }
                    }
                }
                return K[n,cappcity];
            }