c# - C#小数背包o(n logn)解决方案

我在计算分数背包。它对大多数案件都有效，但对某些角落的案件却失败了我实现的算法是标准的我在做一些愚蠢的事情，在获取最优值时，想不出来。请帮忙！

using System;
using System.Collections.Generic;

namespace FractionalKnapsackcsharp
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int n;
            int capacity;
            string n1 = Console.ReadLine();
            n = Convert.ToInt32(n1.Split(' ')[0]);
            capacity = Convert.ToInt32(n1.Split(' ')[1]);

            //read the array values
            string[] answer = new string[n];

            double[] values = new double[n];
            int[] weights = new int[n];
            for (int i = 0; i < answer.Length; i++)
            {
                answer[i] = Console.ReadLine();
                values[i] = Convert.ToDouble(answer[i].Split(' ')[0]);
                weights[i] = Convert.ToInt32(answer[i].Split(' ')[1]);
            }

            double value = get_optimal_value(n, capacity, weights, values);
            Console.WriteLine(Math.Round(value, 4));
        }

        public static double get_optimal_value(int n, int capacity, int[] weights, double[] values)
        {
            double value = 0.0;

          //There should be a better way to handle this scenario, any idea ?
            if (n == 1)
            {
                int a = weights[0] < capacity ? weights[0] : capacity;
                value = value + a * values[0] / weights[0];
                return value;
            }

            Array.Sort(weights, values, Comparer<int>.Create((x, y) => y.CompareTo(x)));

            double[] A = new double[n];
            for (int i = 1; i < n; i++)
            {
                if (capacity == 0) return value;

                int a = weights[i] < capacity ? weights[i] : capacity;
                value = value + a * values[i] / weights[i];
                weights[i] = weights[i] - a;
                A[i] = A[i] + a;
                capacity = capacity - a;
            }
            return value;
        }
    }
}

最佳答案

问题在于排序，下面是工作解决方案：

using System;
using System.Collections.Generic;

namespace FractionalKnapsackcsharp
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int n = 0;
            double capacity;
            string n1 = Console.ReadLine();
            n = Convert.ToInt32(n1.Split(' ')[0]);
            capacity = Convert.ToDouble(n1.Split(' ')[1]);

            double[] values = new double[n];
            double[] weights = new double[n];
            for (int i = 0; i < n; i++)
            {
                var answer = Console.ReadLine();
                values[i] = Convert.ToDouble(answer.Split(' ')[0]);
                weights[i] = Convert.ToDouble(answer.Split(' ')[1]);
            }

            double value = get_optimal_value(n, capacity, values, weights);
            Console.WriteLine(Math.Round(value, 4));
        }

        public static double get_optimal_value(int n, double capacity, double[] values, double[] weights)
        {
            double value = 0.0;

            Array.Sort(values, weights, Comparer<double>.Create((x, y) => y.CompareTo(x)));

            double[] ratio = new double[n];

            for (int i = 0; i < n; ++i)
            {
                ratio[i] = values[i] / weights[i];
            }

            Array.Sort(ratio, weights, Comparer<double>.Create((x, y) => y.CompareTo(x)));
            //Array.Sort(ratio, weights, Comparer<double>.Create((x, y) => x.CompareTo(y)));

            //double[] A = new double[n];
            for (int i = 0; i < n; i++)
            {
                if (capacity == 0) return value;

                double a = weights[i] < capacity ? weights[i] : capacity;
                //value = value + a * (values[i] / weights[i]);
                value = value + a * ratio[i];
                weights[i] = weights[i] - a;
                //A[i] = A[i] + a;
                capacity = capacity - a;
            }
            return value;
        }
    }
}