C＃フラクショナルナップザックo（n logn）解

Question

私はフラクショナルナップザックを計算しています。ほとんどのケースで動作しますが、コーナーケースでは失敗します。私が実装したアルゴリズムは標準的なアルゴリズムです。私はget_optimal_value（）で何か愚かなことをやっています。助けてください ！

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; 
     } 
    } 
} 

Answer 1

問題がソートである、ここでの作業溶液は次のとおりです。

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; 
     } 
    } 
}