What is an algorithm to split N line segments into M segments (N <= M) in a balanced way? -


Probably a trivial question, but I'm looking for an algorithm that can break the N segment segment into M sections (M> = N) in a balanced way (for example that R ^ 2 R-Square Max).

Edit (An example added as requested by the commenter):

For example, N = 5 Length segment: {1, 10, 7, 15, 1} which we want to divide into the M = 7 parts.

  • will be a good solution: {1, 1, 5, 5, 7, 7, 8} (split 15 and 10)
  • One bad solution would be: {1, 1, 5, 5, 5, 7, 10} (split between 15 to 3)

    I think, A greedy algorithm with distance from code> can do as well as Avg , but it was not certain that there are some corner cases with it.

    Thank you,

    In fact this problem not NP-hard, because it is not possible to reconstruct the pieces. As a result, there is an O (M log n) -time algorithm for the problem of determining the reduction in the sum of the squares of the length of the pieces. I will start dividing the count on each segment and put them in the priority queue. (I will soon prioritize priorities). Repeat the following actions - n times: drag the top section (maximum priority), increase its dividing calculation and return it to the queue.

    The priority of each segment is the sum of its squares, the sum of the squares of their imaginary division in another piece by subtracting from the current partition. For example, if 15 is currently divided into two pieces, 7 and 8, and we can divide it into three, 5, 5 and 5, then priority 7 ^ 2 + 8 ^ 2 - 5 ^ 2 - 5 ^ 2 is - 5 ^ 2 = 38. For your example, the initial priority queue 

      15 (1 cut), priority 15 ^ 2 - 7 ^ 2 - 8 ^ 2 = 112 10 (1 Deduction), priority 10 ^ 2 - 5 ^ 2 - 5 ^ 2 = 50 7 (1 cut), priority 7 ^ 2 - 3 ^ 2 - 4 ^ 2 = 24 1 (1 cut), priority 1 ^ 2 - 0 ^ 2 - 1 ^ 2 = 0 1 (1 cut), priority 1 ^ 2 - 0 ^ 2 - 1 ^ 2 = 0.   
     We have divided once, once.  
      10 (1 cut), priority 10 ^ 2 - 5 ^ 2 - 5 ^ 2 = 50 15 (2 deductible), priority 7 ^ 2 + 8 ^ 2 - 5 ^ 2 - 5 ^ 2 - 5 ^ 2 = 38 7 (1 cut), priority 7 ^ 2 - 3 ^ 2 - 4 ^ 2 = 24 1 (1 cut), priority 1 ^ 2 - 0 ^ 2 - 1 ^ 2 = 0 1 ( 1 kata), Priority 1 ^ 2 - 0 ^ 2 - 1 ^ 2 = 0.   
     We have divided once 10 times.  
      15 (2 cut), priority 7 ^ 2 + 8 ^ 2 - 5 ^ 2 - 5 ^ 2 - 5 ^ 2 = 38 10 (2 cut), priority 5 ^ 2 + 5 ^ 2 - 3 ^ 2 - 3 ^ 2 - 4 ^ 2 = 16 7 (1 cut), priority 7 ^ 2 - 3 ^ 2 - 4 ^ 2 = 24 1 (1 cut), priority 1 ^ 2 - 0 ^ 2 - 1 ^ 2 = 0 1 (1 cut), priority 1 ^ 2 - 0 ^ 2 - 1 ^ 2 = 0.   
     We stop here; 15, the next will be for 1, 1, 5, 5, 5, 5, 5, 7.  
     The reason for this is that the "greedy" algorithm is optimal because, because of dividing more than one segment, the return pieces are free and reduced in an accurate technical sense (supermodulary).

Comments

Post a Comment

Popular posts from this blog

Java - Error: no suitable method found for add(int, java.lang.String) -

I'm in the middle of homework work and I'm stuck. At this point in my code, I think that I should have a GUI window that opens and allows me to type "inserted text number". Notice is not going anywhere but at this point, If I pass through the problem then it will be in a linked list. I am getting two of the same error for the lines. Add (index, element); And I can not seem to get past it, there is no suitable method for the error "add (int, java. string string)". Code is below, please advise. To clarify - this will not be a method error because it is a linked list. There should not be any way involved. import java.awt. *; Import java.awt.event. *; Import javax.swing. *; Import java.util. *; Import java.util.Scanner; Import java.util.LinkedList; Public class TopTenList JFrame {Private TopTenList tt; See the Private JTextArea list; Private JTextField cmdTextField; Private JTextField resultsTestfield; // This GUI window is the code for the public toptist...
Read more

java - JPA TypedQuery: Parameter value element did not match expected type -

I am using JPA 2.0 and getting the following code in the DAO layer: Public Zero Test () {string key = "status"; String [] Conditions = {"A", "B"}; & Lt; TestTable & gt; Results = Search (Keys, Conditions); } Public listing & lt; TestTable & gt; Search (string key, object value error) {string sql = "test ndf to testlet and jade nand." + Key + "in:" + key; TypedQuery & LT; TestTable & gt; Query = entityManager.createQuery (SQL, TestTable.class); Query.setParameter (key, Arrays.asList (valueArr)) / *** Error Line *** Return query.getResultList (); } In the above error line, it throws the following exception: java.lang.IllegalArgumentException: parameter value element [[Ljava.lang.String; @ cbe5bc] did not match the expected type [java.lang.String] Why is this expected type string while actually this string []? Please help! Note: This is derived from the normal routine and is a simplified code. I can no...
Read more

c++ - static template member variable has internal linkage but is not defined -

Yes, I know, there is a question with almost the same title, but it refers to a different situation. Error message) In my case, I have a .cpp file with a big named designation name (implementation details). There is a property class template with a static data member in that name space, which I need to access from outside the unknown namespace. I give it a little bit of meat: file.hpp namespace Bar {template & lt; Typename A & gt; Struct foo {static_assert (is_same & lt; a, float & gt; :: value} is_same & lt; a, double>: value, ""); Fixed zero set_static_var (a const & x); // ...}; } and file.cpp namespace {template & lt; Typename A & gt; Struct foo_traits {// supports the implementation of several static code bars: foo & lt; & Gt; Fixed A data; }; The template's & lt; & Gt; Float foo_traits & lt; Float & gt; :: datum; // No change if this is in the global namespace template & lt; & Gt; Doub...
Read more