समूह के खर्च बराबर बाँटकर देखें कि कौन किसे देता है। अधिकतम 16 गैर-शून्य बकायों के लिए न्यूनतम भुगतानों की योजना और बड़े समूहों के लिए अनुमानित योजना मिलती है।
लेखक: AdminAI लेखन टूल से मसौदा तैयारअपडेट किया गया जाँचे गए उदाहरण: 4
कुल खर्च: $195.50; हर व्यक्ति का हिस्सा: $48.88। 3 भुगतानों में हिसाब पूरा: Jo, Alex को $48.88 चुकाए; Priya, Alex को $18.88 चुकाए; Sam, Alex को $3.38 चुकाए।
| से | में | राशि |
|---|---|---|
| Jo | Alex | $48.88 |
| Priya | Alex | $18.88 |
| Sam | Alex | $3.38 |
सूत्र में P_i हर व्यक्ति का भुगतान, n समूह का आकार, q बराबर हिस्सा, b_i उसका शेष, k गैर-शून्य शेषों की संख्या और G_max शून्य-योग समूहों की अधिकतम संख्या है। N_min न्यूनतम भुगतान हैं; सटीक खोज अधिकतम 16 गैर-शून्य शेषों पर चलती है।
Alex 120 − 48.875 = 71.125; Sam 45.5 − 48.875 = −3.375; Priya 30 − 48.875 = −18.875; Jo 0 − 48.875 = −48.875
4 लोगों के शेष गैर-शून्य हैं। g लोगों का हर शून्य-योग समूह g − 1 भुगतानों में निपटता है: कुल 3 भुगतान।
दिखाने के लिए राशि सेंट तक गोल है, इसलिए भुगतान सटीक शेष से एक सेंट से कम अलग हो सकता है।
हर व्यक्ति का बराबर हिस्सा कुल खर्च को लोगों की संख्या से भाग देने पर मिलता है। शेष = उस व्यक्ति का भुगतान − उसका हिस्सा। धनात्मक शेष पर पैसा मिलना है, ऋणात्मक पर देना है। कैलकुलेटर ऐसे अधिकतम समूह खोजता है जिनके शेष का योग शून्य हो; g लोगों का ऐसा समूह अधिकतम g − 1 भुगतानों में हिसाब पूरा कर सकता है।
डिफ़ॉल्ट उदाहरण में Alex, Sam और Priya ने कुल 195.50 दिए और Jo ने कुछ नहीं दिया। चारों का हिस्सा 48.875 है। तीन भुगतानों में हिसाब पूरा होता है: Jo से Alex को 48.88, Priya से Alex को 18.88 और Sam से Alex को 3.38।
सबसे कम भुगतान खोजना सामान्य स्थिति में NP-कठिन है (Verhoeff, 2004)। इसलिए सटीक खोज अधिकतम 16 गैर-शून्य शेष वाले लोगों पर चलती है। बड़े समूह में सबसे बड़ा देनदार सबसे बड़े लेनदार को चुकाता है। दिखाई गई राशि सेंट तक गोल है; हर भुगतान सटीक शेष से एक सेंट से कम अलग हो सकता है।
सभी खर्च जोड़कर उन लोगों की संख्या से भाग दें जो खर्च साझा करते हैं। हर व्यक्ति का शेष = उसका भुगतान − बराबर हिस्सा। धनात्मक शेष पर उसे पैसा मिलना है और ऋणात्मक पर देना है। जिसने कुछ नहीं दिया, उसका नाम भी लोगों की सूची में रखें।
उदाहरण में Alex ने 120, Sam ने 45.50 और Priya ने 30 दिए; Jo ने कुछ नहीं दिया। कुल 195.50, चारों का हिस्सा 48.875 और Alex का शेष +71.125 है। बाकी शेष −3.375, −18.875 और −48.875 हैं। Jo, Priya और Sam से Alex को तीन भुगतान करने पर सटीक हिसाब पूरा होता है।
कैलकुलेटर ऐसे अलग समूह खोजता है जिनके शेष का योग शून्य हो। g लोगों का समूह g − 1 भुगतानों में निपट सकता है। पाँच लोगों के शेष +4, +3, +2, −5, −4 हों तो दो समूह बनाकर 3 भुगतान पर्याप्त हैं; सबसे बड़ी राशियाँ पहले मिलाने में 4 लगते हैं। Verhoeff का शोध बताता है कि सामान्य स्थिति में न्यूनतम खोजना कठिन है।
सटीक खोज अधिकतम 16 गैर-शून्य शेषों तक है। बड़े समूह में सबसे बड़ा देनदार सबसे बड़े लेनदार को चुकाता है; यह हिसाब निपटाता है, पर न्यूनतम संख्या का दावा नहीं करता।
48.875 का भुगतान सेंट में सटीक नहीं हो सकता। ऊपर के भुगतान 48.88, 18.88 और 3.38 दिखते हैं; उनका योग 71.14 है, सटीक 71.125 से 1.5 सेंट अधिक। पहले बराबर हिस्से को गोल करने के बजाय अंत के भुगतानों को ही गोल करें।
| स्थिति | कुल खर्च | बराबर हिस्सा | भुगतान |
|---|---|---|---|
| मूल उदाहरण | 195.500000 | 48.875000 | 3.000000 |
| न्यूनतम योजना बेहतर | 50.000000 | 10.000000 | 3.000000 |
| सबका हिसाब बराबर | 30.000000 | 10.000000 | 0.000000 |
| छूटा भुगतानकर्ता | 120.000000 | 40.000000 | 1.000000 |
| आवर्ती दशमलव हिस्सा | 10.000000 | 3.333333 | 2.000000 |
आवर्ती हिस्से की पंक्ति में एक व्यक्ति ने तीन लोगों के लिए 10 दिए हैं। छूटे भुगतानकर्ता के उदाहरण में Alex, Sam, Kim के भुगतान 60, 20, 40 हैं; Kim को जोड़कर हिस्सा 40 और Sam से Alex को भुगतान 20 है।
एक पंक्ति का रूप अजय, 120, भोजन रखें; दूसरा भुगतान अगली पंक्ति में लिखें। राशियाँ देवनागरी अंकों में भी दी जा सकती हैं। नाम कॉमा से अलग सूची में दें। अंग्रेज़ी Alex paid 120 for food भी स्वीकार है; सामान्य हिंदी वाक्य के बजाय दिखाया गया सूची-रूप इस्तेमाल करें।
सिर्फ कुछ लोगों के खर्च अलग गणना में बाँटें। सभी चार के होटल का 400 और केवल Sam/Priya की ट्रेन का 60 एक ही बराबर विभाजन में नहीं जाने चाहिए। सभी रसीदें एक मुद्रा में बदलें। यात्रा की योजना के लिए यात्रा बजट, और एक रेस्तराँ बिल के लिए टिप और बिल विभाजन उपयोग करें।
जाँच का स्रोत: शेष −48.875, −18.875, −3.375 को सम-अंक नियम से सेंट तक गोल किया; सभी उपसमूह खोजने पर 3 भुगतान
जाँच का स्रोत: 5 − 2 = 3; सबसे बड़ी राशियाँ पहले मिलाने पर 4
जाँच का स्रोत: उदाहरण की जाँच: परिभाषा के अनुसार हर शेष 0 है
जाँच का स्रोत: उदाहरण की जाँच: हाथ से गणना: 120/3 = 40; Alex +20, Sam −20, Kim 0
सभी खर्च जोड़कर लोगों की संख्या से भाग दें। फिर हर व्यक्ति के दिए पैसे से उसका हिस्सा घटाएँ। चार लोगों में 195.50 का हिस्सा 48.875 है। Alex ने 120 दिए, इसलिए उसे 71.125 मिलने हैं; Jo ने कुछ नहीं दिया, इसलिए उसे 48.875 देने हैं। ऋणात्मक शेष वाले लोग धनात्मक शेष वालों को भुगतान करते हैं।
गैर-शून्य शेष वाले लोगों की संख्या से अधिकतम एक कम। शून्य-योग वाले अलग समूह बन सकें तो और कम, क्योंकि g लोगों का समूह g − 1 भुगतानों में निपटता है। Tom Verhoeff के 2004 के शोध में न्यूनतम खोजना कम से कम subset-sum समस्या जितना कठिन बताया गया है; इसलिए सटीक उत्तर के लिए खोज ज़रूरी है।
उससे शून्य-योग समूह छूट सकते हैं। A से E के शेष +4, +3, +2, −5 और −4 हों तो सबसे बड़ी राशियाँ मिलाने में 4 भुगतान लगते हैं। {+4, −4} और {+3, +2, −5} समूह बनाएँ तो पहली जोड़ी में 1 और दूसरे समूह में 2, कुल 3 भुगतान पर्याप्त हैं।
यह उपकरण हर खर्च को सूची के सभी लोगों में बराबर बाँटता है। केवल दो लोगों के ट्रेन टिकट जैसे खर्च के लिए उन्हीं लोगों के साथ अलग गणना करें, फिर दोनों योजनाओं के भुगतान जोड़ें। इससे देनदारी निपट जाती है, पर एक संयुक्त सर्वोत्तम योजना से एक-दो अधिक भुगतान लग सकते हैं।
इस कैलकुलेटर में स्वतंत्र स्रोतों के उत्तरों वाले 4 हल किए गए उदाहरण शामिल हैं। ये परीक्षण समूह में चलते हैं और आप इन्हें यहाँ भी चला सकते हैं।