जावा: बैचिंग पूर्णांक

Question

मैं सोच रहा था कि प्रोसेसिंग समय के संदर्भ में संख्याओं के दिए गए सेट को बैच करने का सबसे अच्छा तरीका क्या है। लें आइटम: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8,

बैच प्रोसेसिंग समय सीमा सेट है, तो 20, कहने के लिए तो के संभावित समूह (मद 1 से 9 के एक प्रसंस्करण समय है, आइटम 2 18 के प्रसंस्करण समय, आदि है) बैचों में आइटम होंगे: {1, 3, 5} {2} {4, 6} {8, 9} {7, 10} (समूह 1 9 + 7 + 4 = 20) इत्यादि है, इसलिए 5 बैचों की वस्तुओं को बनाया गया है जहां सामग्री < = 20.

आदर्श रूप में मैं उन्हें कम से कम क्रमबद्ध करना चाहता हूं जितना संभव हो सके समूह। ऊपर के मामले 20 की सामग्री सीमा के साथ 5 समूहों की एक न्यूनतम है ...

धन्यवाद

Answer 1

बैच प्रोसेसिंग समय सीमा 20, कहने के लिए सेट है, तो ...

तो मुझे लगता है कि बैच प्रसंस्करण समय सीमा से अधिक कोई तत्व नहीं है। यहां मेरा दृष्टिकोण है:

• सबसे पहले आइटम को सॉर्ट करें। तब सूची के लिए 2 संकेत मिलता है, एक सूचकांक 0 (बाएं सूचक) और पिछले सूचकांक (राइट सूचक) पर एक दूसरे पर है।
• दाएं-पॉइंटर का तत्व लें और इसे एक उपन्यास में जोड़ें। बाएं पॉइंटर के तत्व लें और इसे उसी उपन्यास में जोड़ें। यदि की राशि सब्लिस्ट में तत्व सीमा से कम है, तो बाएं-पॉइंटर अपडेट करें ( इसे अगले तत्व पर सेट करें) और इसे जोड़ने का प्रयास करें। उपशीर्षक भरने तक इस प्रक्रिया को जारी रखें।
• फिर अगला उपन्यास भरना शुरू करें। सभी तत्वों को का निर्माण उपन्यासों का उपभोग करें। जावा में

कार्यान्वयन:

int[] input = { 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 }; // Input items. 
Arrays.sort(input); // Sort the items. 
int left = 0, right = input.length - 1; // Left and right pointers. 
int remainder = 0, limit = 20; 

// list of groups. 
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); 

while (right >= left) 
{ 
    ArrayList<Integer> subList = new ArrayList<Integer>(); 
    list.add(subList); 
    // Add the current maximum element. 
    subList.add(input[right]); 
    if (right == left) 
     break; 
    remainder = limit - input[right]; 
    right--; 

    // Add small elements until limit is reached. 
    while (remainder > input[left]) { 
     subList.add(input[left]); 
     remainder = remainder - input[left]; 
     left++; 
    } 

    remainder = 0; // Reset the remainder. 
} 

मुद्रण समूह:

for (ArrayList<Integer> subList : list) 
{ 
    for (int i : subList) 
     System.out.print(i + " "); 
    System.out.println(); 
} 

आउटपुट: (प्रत्येक पंक्ति संख्या के एक समूह के नाम हैं)

18 
15 3 
11 4 
9 7 
9 8 
8 

Answer 2

1. मूल्य के साथ सबसे बड़ी आइटम खोजने के लिए सेट से सबसे बड़ी ले लो और एस (आइटम 2, मूल्य 18) एक नया सेट में डाल
2. कोशिश < = (20 - 18): कोई नहीं, जोड़ने सेट की एक सूची में एस।
3. अगर में खाली गोटो 1

पुनरावृत्ति नहीं है:

      IN: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 
S1 (18) : 2:18   IN: 9, _, 7, 8, 4, 9, 11, 15, 3, 8 
S2 (19) : 8:15, 5:4  IN: 9, _, 7, 8, _, 9, 11, _, 3, 8 
S3 (20) : 7:11, 1:9  IN: _, _, 7, 8, _, 9, _, _, 3, 8 
S4 (20) : 6: 9, 4:8, 0:3 IN: _, _, 7, _, _, _, _, _, _, 8 
S5 (15) : 10: 8, 3:7  IN: _, _, _, _, _, _, _, _, _, _ 

कोड:

public class Knapsack { 
    public static void knapsack(int capacity, int[] values, List<int[]> indices) { 
     int[]   in   = Arrays.copyOf(values, values.length); 
     List<Integer> workspace = new LinkedList<>(); 
     int    wCapacity = capacity; 
     boolean   inProgress = true; 
     while(inProgress) { 
     int greatestValue = -1; 
     int greatestIndex = -1; 
     for(int i = 0; i < in.length; ++i) { 
      int value = in[i]; 
      if( value > Integer.MIN_VALUE 
       && greatestValue < value && value <= wCapacity) 
      { 
       greatestValue = value; 
       greatestIndex = i; 
      } 
     } 
     if(greatestIndex >= 0) { 
      workspace.add(greatestIndex); 
      in[greatestIndex] = Integer.MIN_VALUE; 
      wCapacity -= greatestValue; 
     } else if(workspace.isEmpty()) { 
      inProgress = false; 
     } else { 
      int[] ws = new int[workspace.size()]; 
      for(int i = 0; i < workspace.size(); ++i) { 
       ws[i] = workspace.get(i).intValue(); 
      } 
      indices.add(ws); 
      workspace = new LinkedList<>(); 
      wCapacity = capacity; 
     } 
     } 
    } 
    static void print(int[] values, List<int[]> indices) 
    { 
     int r = 0; 
     for(int[] t : indices) { 
     String items = ""; 
     int sum = 0; 
     for(int index : t) { 
      int value = values[index]; 
      if(! items.isEmpty()) { 
       items += ", "; 
      } 
      items += index + ":" + value; 
      sum += value; 
     } 
     System.out.println("S" + ++r + " (" + sum + ") : " + items); 
     } 
    } 
    public static void main(String[] args) { 
     int[]   values = { 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 }; 
     List<int[]> indices = new LinkedList<>(); 
     knapsack(20, values, indices); 
     print(values, indices); 
    } 
} 

परिणाम:

S1 (18) : 1:18 
S2 (19) : 7:15, 4:4 
S3 (20) : 6:11, 0:9 
S4 (20) : 5:9, 3:8, 8:3 
S5 (15) : 9:8, 2:7