5
के लिए कवर बॉक्स की न्यूनतम संख्या मेरे पास एक बाइनरी मैट्रिक्स एन * एम (0 और 1) है। समस्या गैर-अतिव्यापी बक्से जिसका तत्वों सभी 1.द्विआधारी मैट्रिक्स
उदाहरण हैं के साथ सभी 1 के कवर करने के लिए है:
1111
0110
0110
बॉक्स प्रत्येक समन्वय (x,y,lx,ly) में निर्देशांक और लंबाई के साथ प्रतिनिधित्व करते हैं हो सकता है। यह उदाहरण 2 बक्से { (0,0,1,4), (1,1,2,2) } के साथ कवर किया गया है।
मैं देख रहा हूं कि न्यूनतम संख्या में बक्से के साथ कवर कैसे ढूंढें।
धन्यवाद
बक्से हैं/
कुछ शोध के बाद, मैं अनुमानी अनुज जैन द्वारा कागजात में वर्णित के आधार पर समाधान लागू ओवरलैप करने की अनुमति है? –
@ जेफ: निर्दिष्ट समस्या के लिए, आपको ओवरलैपिंग से कोई लाभ नहीं मिलेगा। –
आपको यह उपयोगी मिल सकता है: http://stackoverflow.com/questions/4701887/find-the-set-of-largest-contiguous-rectangles-to-cover-multiple-areas/4701966#4701966 – biziclop