सुझाव भिन्न मान

Question

की वस्तुओं को वितरित करने के मैं निम्नलिखित समस्या है:

को देखते हुए एन वस्तुओं (एन < 30) एक "K" निरंतर यानी कश्मीर के विभिन्न मानों कई, 2k, 3k, 4k, 6k की , 8k, 12k, 16k, 24k और 32k, मुझे एक एल्गोरिदम की आवश्यकता है जो सभी वस्तुओं को एम प्लेयर (एम < = 6) में वितरित करेगा ताकि प्रत्येक खिलाड़ी को प्राप्त होने वाले ऑब्जेक्ट्स का कुल मूल्य जितना संभव हो सके दूसरे शब्दों में, मैं सभी वस्तुओं को सभी संभवतः सबसे अच्छे तरीके से वितरित करना चाहता हूं)।

संपादित करें: सबसे अच्छे वितरण से मेरा मतलब है कि वस्तुओं के मूल्य के बीच का अंतर किसी भी दो खिलाड़ियों को मिलता है। एक और समान मामला होगा: मेरे पास विभिन्न मूल्यों के एन सिक्के हैं और मुझे उन्हें एम खिलाड़ियों के बीच समान रूप से विभाजित करने की आवश्यकता है; कभी-कभी वे बिल्कुल विभाजित नहीं होते हैं और मुझे वितरण के अगले सबसे अच्छे मामले को खोजने की आवश्यकता होती है (जहां कोई खिलाड़ी नाराज नहीं होता है क्योंकि किसी और को बहुत अधिक पैसा मिलता है)।

मुझे इसे हल करने के लिए कोड (छद्म) कोड की आवश्यकता नहीं है (यह भी एक होमवर्क नहीं है :)), लेकिन मैं इसे हल करने वाले एल्गोरिदम के किसी भी विचार या लिंक की सराहना करूंगा।

धन्यवाद!

Answer 1

समस्या दृढ़ता से एनपी-पूर्ण है। इसका मतलब है कि उचित समय में सही समाधान सुनिश्चित करने का कोई तरीका नहीं है। (देखें 3-partition-problem, धन्यवाद पॉल)।

इसके बजाय आप एक अच्छे अनुमानित समाधान जनरेटर के लिए जाना चाहेंगे। ये अक्सर बहुत ही कम समय में इष्टतम उत्तर के बहुत करीब हो सकते हैं। मैं Simulated Annealing तकनीक की सिफारिश कर सकता हूं, जिसे आप अन्य एनपी-पूर्ण समस्याओं के टन के लिए भी उपयोग करने में सक्षम होंगे।

1. बेतरतीब ढंग से आइटम का वितरण करें:

   विचार यह है।

2. लगातार दो यादृच्छिक खिलाड़ियों के बीच यादृच्छिक स्वैप बनाते हैं, जब तक कि यह सिस्टम को अधिक निष्पक्ष बनाता है, या केवल थोड़ा कम निष्पक्ष (विवरण के लिए विकी देखें)।
3. जब आपके पास पर्याप्त कुछ उचित है, या आप समय से बाहर हो गए हैं तो रोकें।

यह समाधान 'लालची' एल्गोरिदम से बहुत अधिक मजबूत है। लालची एल्गोरिदम वह है जहां आप लगातार 'सबसे गरीब' खिलाड़ी को सबसे बड़ा आइटम जोड़ते हैं। एक टेस्टकेस का एक उदाहरण जहां लालची विफल रहता है [10,9,8,7,7,5,5] है।

---

मैंने आपके लिए एसए का कार्यान्वयन किया था। यह शैक्षिक उद्देश्यों के लिए सख्ती से विकी लेख का पालन करता है। यदि आप इसे अनुकूलित करते हैं, तो मैं कहूंगा कि 100x सुधार अवास्तविक नहीं होगा।

from __future__ import division 
import random, math 

values = [10,9,8,7,7,5,5] 
M = 3 
kmax = 1000 
emax = 0 

def s0(): 
    s = [[] for i in xrange(M)] 
    for v in values: 
     random.choice(s).append(v) 
    return s 

def E(s): 
    avg = sum(values)/M 
    return sum(abs(avg-sum(p))**2 for p in s) 

def neighbour(s): 
    snew = [p[:] for p in s] 
    while True: 
     p1, p2 = random.sample(xrange(M),2) 
     if s[p1]: break 
    item = random.randrange(len(s[p1])) 
    snew[p2].append(snew[p1].pop(item)) 
    return snew 

def P(e, enew, T): 
    if enew < e: return 1 
    return math.exp((e - enew)/T) 

def temp(r): 
    return (1-r)*100 

s = s0() 
e = E(s) 
sbest = s 
ebest = e 
k = 0 
while k < kmax and e > emax: 
    snew = neighbour(s) 
    enew = E(snew) 
    if enew < ebest: 
     sbest = snew; ebest = enew 
    if P(e, enew, temp(k/kmax)) > random.random(): 
     s = snew; e = enew 
    k += 1 

print sbest 

अद्यतन: Branch'n'Bound के साथ चारों ओर खेलने के बाद, मैं अब का मानना ​​है के रूप में यह एन = 30, एक दूसरे के भीतर एम = 6 मामले के लिए एकदम सही परिणाम देता है बेहतर होने के लिए इस विधि। हालांकि मुझे लगता है कि आप सिमुलेट एनीलिंग दृष्टिकोण के साथ उतना ही खेल सकते हैं जितना ज्यादा।

Answer 2

इस बारे में कैसे:

के मूल्यों को ऑर्डर करें। खिलाड़ियों को आदेश दें।

के मूल्यों पर लूप अगले खिलाड़ी को अगले व्यक्ति को दे रहा है। जब आप खिलाड़ियों के अंत तक पहुंच जाते हैं, तो चारों ओर मुड़ें और खिलाड़ियों को विपरीत दिशा में के मूल्यों को जारी रखें।

Answer 3

बार-बार उपलब्ध ऑब्जेक्ट को उस खिलाड़ी के लिए सबसे बड़ा मूल्य प्रदान करें जिसके पास उसके लिए आवंटित वस्तुओं का कम से कम मूल्य है।

Answer 4

30^6 इतना बड़ा नहीं है (यह 1 बिलियन से कम है)। हर संभावित आवंटन के माध्यम से जाएं, और जो भी उपाय आप परिभाषित करते हैं, उसे चुनें।

Answer 5

यह जस्टिन पील के जवाब की एक सीधी-सपाट दिया गया है:

M = 3 
players = [[] for i in xrange(M)] 

values = [10,4,3,1,1,1] 
values.sort() 
values.reverse() 
for v in values: 
    lowest=sorted(players, key=lambda x: sum(x))[0] 
    lowest.append(v) 

print players 
print [sum(p) for p in players] 

मैं अजगर के साथ एक शुरुआत कर रहा हूँ, लेकिन यह ठीक से काम करने लगता है। इस उदाहरण प्रिंट होगा

[[10], [4, 1], [3, 1, 1]] 
[10, 5, 5] 

Answer 6

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

उद्देश्य कार्यान्वयन, जो शायद सी # में पारदर्शी है में छोटे सुधार के साथ लालची समाधान का इस्तेमाल किया गया:

static List<List<int>> Dist(int n, IList<int> values) 
{ 
    var result = new List<List<int>>(); 
    for (int i = 1; i <= n; i++) 
     result.Add(new List<int>()); 
    var sortedValues = values.OrderByDescending(val => val);//Assume the most efficient sorting algorithm - O(N log(N)) 
    foreach (int val in sortedValues) 
    { 
     var lowest = result.OrderBy(a => a.Sum()).First();//This can be done in O(M * log(n)) [M - size of sortedValues, n - size of result] 
     lowest.Add(val); 
    } 
    return result; 
} 

इस स्तर के बारे में:

var lowest = result.OrderBy(a => a.Sum()).First();//This can be done in O(M * log(n)) [M - size of sortedValues, n - size of result] 

विचार यह है कि सूची हमेशा क्रमबद्ध होती है (इस कोड में यह ऑर्डरबी द्वारा किया जाता है)। आखिरकार, यह सॉर्टिंग ओ (लॉग (एन)) से अधिक नहीं लेती है - क्योंकि हमें केवल एक आइटम को एक क्रमबद्ध सूची में INSERT करने की आवश्यकता है - जिसे बाइनरी खोज के समान ही लेना चाहिए। क्योंकि हमें क्रमबद्ध करने के लिए इस चरण को दोहराने की आवश्यकता है। तरंगों के समय, पूरे एल्गोरिदम ओ (एम * लॉग (एन)) में चलता है।

तो, शब्दों में, यह rephrased जा सकता है के रूप में: दोहराएँ नीचे तक तुम Values मूल्यों खत्म कदम: 1. अगर यह खिलाड़ी अभी भी छोटी से छोटी राशि है छोटे कद के खिलाड़ी के लिए सबसे बड़ा मूल्य जोड़े 2. 3. यदि हां, तो चरण 1 पर जाएं। 4. सॉर्ट किए गए खिलाड़ियों की सूची के लिए अंतिम-प्राप्त-प्राप्त प्लेयर डालें

चरण 4 ओ (लॉग (एन)) चरण है - जैसा कि सूची है हमेशा क्रमबद्ध।

Answer 7

कुछ लोगों द्वारा सुझाया गया लालची समाधान सबसे अच्छा विकल्प जैसा लगता है, मैंने इसे कुछ यादृच्छिक मूल्यों के साथ कई गुना भाग लिया, और ऐसा लगता है कि यह हर बार सही लगता है।
यदि यह इष्टतम नहीं है, यह बहुत करीब कम से कम है, और यह (मैं अभी गणित कर परेशान नहीं किया जा सकता है)
सी # कार्यान्वयन हे (एनएम) में चलाता है या तो:

static List<List<int>> Dist(int n, IList<int> values) 
{ 
    var result = new List<List<int>>(); 
    for (int i = 1; i <= n; i++) 
     result.Add(new List<int>()); 
    var sortedValues = values.OrderByDescending(val => val); 
    foreach (int val in sortedValues) 
    { 
     var lowest = result.OrderBy(a => a.Sum()).First(); 
     lowest.Add(val); 
    } 
    return result; 
}