बराबर आकार में एक ऐरे को विभाजित करें, जैसे दिए गए फ़ंक्शन का मान न्यूनतम

Question

मुझे निम्न समस्या कथन में आया है।

आप आकार N के प्राकृतिक संख्याओं की एक सूची है और आप, दो सूचियों A और आकार N/2 की B में मानों वितरित करना होगा ताकि A तत्वों की चुकता राशि B के गुणन के सबसे नजदीक संभव है तत्वों।

उदाहरण: सूची पर विचार करें 7 11 1 9 10 3 5 13 9 12.
अनुकूलित वितरण है:
सूची A: 5 9 9 12 13
सूची B: 1 3 7 10 11
जो अंतर abs ((5 + 9 + 9 + 12 + 13)^2 - (1 * 3 * 7 * 10 * 11)) = 6
आपके प्रोग्राम को आउटपुट 6 होना चाहिए, जो न्यूनतम है अंतर प्राप्त किया जा सकता है।

मैं क्या कोशिश की है:

मैं इस समस्या को हल करने के लिए लालची दृष्टिकोण की कोशिश की है। मैंने दो चर sum और mul लिया। अब मैंने दिए गए सेट से तत्वों को एक-एक करके लेना शुरू कर दिया है और इसे दोनों चरों में जोड़ने की कोशिश की है और वर्तमान योग और गुणा के वर्ग की गणना की है। अब तत्व को दो सेटों में से एक में अंतिम रूप दें, जैसे कि संयोजन न्यूनतम संभव मूल्य देता है।

लेकिन यह दृष्टिकोण दिए गए उदाहरण में काम नहीं कर रहा है। मैं यह नहीं समझ सकता कि यहां किस दृष्टिकोण का उपयोग किया जा सकता है।

मैं समाधान के लिए सटीक कोड मांगने के लिए नहीं हूं। कोई भी संभावित दृष्टिकोण और यह क्यों काम कर रहा है, ठीक होगा।

संपादित करें:

स्रोत: CodinGame, Community puzzle

Answer 1

मैं अगर वहाँ बहुपद समय में किसी भी सटीक समाधान यकीन नहीं है। लेकिन आप एक अनुरूपित एनीलिंग आधारित दृष्टिकोण का प्रयास कर सकते हैं।

मेरे दृष्टिकोण होगा:

1. प्रारंभ लिस्टा और listB एक यादृच्छिक राज्य
संभावना पी रन लालची कदम के साथ
2. करने के लिए, अन्यथा एक यादृच्छिक कदम
3. राज्य का ट्रैक रखें और संबंधित त्रुटि चलाने (हैश मैप के साथ)

लालची चरण: त्रुटि को अनुकूलित करने वाली सूची के बीच एक तत्व खोजें जिसे आप स्थानांतरित कर सकते हैं।

यादृच्छिक चरण: इन दोनों सेटों में से किसी एक से यादृच्छिक तत्व चुनें और त्रुटि की गणना करें। अगर त्रुटि बेहतर है, तो इसे रखें। अन्यथा q की संभावना के साथ इसे रखें।

इन दोनों चरणों में से किसी एक पर यह सुनिश्चित कर लें कि नया राज्य पहले ही खोज नहीं हुआ है (या कम से कम इसे हतोत्साहित करें)।

एक छोटे मूल्य (< 0.1) और q के लिए पी सेट त्रुटि अंतर पर निर्भर कर सकता है।

Answer 2

बाहर आज़माएं:

import java.util.Arrays; 

public class Test { 

    public static void main(String [] args){ 
     int [] arr = {7, 11, 1, 9, 10, 3, 5, 13, 9, 12}; 
     int [][] res = combinations(5, arr); 
     int N = Arrays.stream(arr).reduce(1, (a, b) -> a * b); 
     int min = Integer.MAX_VALUE; 
     int [] opt = new int [5]; 
     for (int [] i : res){ 
      int k = (int) Math.abs(Math.pow(Arrays.stream(i).sum(), 2) - N/(Arrays.stream(i).reduce(1, (a, b) -> a * b))); 
      if(k < min){ 
       min = k; 
       opt = i; 
      } 
     } 
     Arrays.sort(opt); 
     System.out.println("minimum difference is "+ min + " with the subset containing this elements " + Arrays.toString(opt)); 
    } 

    // returns all k-sized subsets of a n-sized set 
    public static int[][] combinations(int k, int[] set) { 
     int c = (int) binomial(set.length, k); 
     int[][] res = new int[c][Math.max(0, k)]; 
     int[] ind = k < 0 ? null : new int[k]; 
     for (int i = 0; i < k; ++i) { 
      ind[i] = i; 
     } 
     for (int i = 0; i < c; ++i) { 
      for (int j = 0; j < k; ++j) { 
       res[i][j] = set[ind[j]]; 
      } 
      int x = ind.length - 1; 
      boolean loop; 
      do { 
       loop = false; 
       ind[x] = ind[x] + 1; 
       if (ind[x] > set.length - (k - x)) { 
        --x; 
        loop = x >= 0; 
       } else { 
        for (int x1 = x + 1; x1 < ind.length; ++x1) { 
         ind[x1] = ind[x1 - 1] + 1; 
        } 
       } 
      } while (loop); 
     } 
     return res; 
    } 
    // returns n choose k; 
    // there are n choose k combinations without repetition and without observance of the sequence 
    // 
    private static long binomial(int n, int k) { 
     if (k < 0 || k > n) return 0; 
     if (k > n - k) { 
      k = n - k; 
     } 
     long c = 1; 
     for (int i = 1; i < k+1; ++i) { 
      c = c * (n - (k - i)); 
      c = c/i; 
     } 
     return c; 
    } 
} 

कोड this stackoverflow answer से लिया, यह भी युग्म के बारे में this विकिपीडिया लेख पर एक नज़र डालें।