2017-09-25 23 views
7

मैं निम्नलिखित समस्या को हल करने की कोशिश कर रहा हूँ:सबसे छोटा एन-बिट पूर्णांक ग कश्मीर 1-बिट है और है कि छ दो एन-बिट पूर्णांकों का योग है, ज बिट्स 1 (गतिशील प्रोग्रामिंग) के लिए सेट

छोटी से छोटी n-बिट पूर्णांक ग कश्मीर 1-बिट है और है कि जी, एच बिट्स 1. जी, एच सेट दो एन-बिट पूर्णांकों का योग है कि पता लगाएं, k < = n

प्रारंभ करने के लिए, यहां एन-बिट पूर्णांक का अर्थ है कि हम सभी n बिट्स, यानी अधिकतम उपयोग कर सकते हैं। ऐसे पूर्णांक का मान 2^n - 1 है। वर्णित पूर्णांक बिल्कुल मौजूद नहीं हो सकता है। यह स्पष्ट है कि k > g + h में कोई समाधान नहीं है और g + h = k के लिए उत्तर केवल 2^k - 1 है (पहले k बिट्स 1-बिट्स, k - n सामने में शून्य हैं)।

कार्यक्रम करने के लिए माना जाता है के कुछ उदाहरण दिए के लिए के रूप में:

g = h = k = 4, n = 10 : 
0000001111 + 0000001111 = 0000011110 
15 + 15 = 30 (30 should be the output) 


(4, 6, 5, 10): 
0000011110 + 0000111111 = 0001011101 
30 + 63 = 93 

(30, 1, 1, 31): 
1 + (2^30 - 1) = 2^30 

मैं इसके बारे में लगता है के रूप में, यह एक गतिशील प्रोग्रामिंग समस्या है और मैं निम्नलिखित दृष्टिकोण चुन लिया है: dp[g][h][k][n][c] होने दो वर्णित पूर्णांक और c ले जाने के लिए एक वैकल्पिक बिट है। मैं निम्नतम आदेश बिट्स के आधार पर संभावित रकम का पुनर्निर्माण करने का प्रयास करता हूं। तो, dp[g][h][k][n + 1][0]

(0, 0):  dp[g][h][k][n][0] 
(0, 0): 2^n + dp[g][h][k - 1][n][1] 
(1, 0): 2^n + dp[g - 1][h][k - 1][n][0] 
(0, 1): 2^n + dp[g][h - 1][k - 1][n][0] 

इसी तरह के कम से कम है, dp[g][h][k][n + 1][1]

(1, 1): dp[g - 1][h - 1][k][n][0] 
(1, 1): dp[g - 1][h - 1][k - 1][n][1] + 2^n 
(1, 0): dp[g - 1][h][k][n][1] 
(0, 1): dp[g][h - 1][k][n][1] 

की न्यूनतम विचार यह है कि मुश्किल नहीं है, लेकिन मैं वास्तव में इस तरह की चीजों और मेरे एल्गोरिथ्म नहीं करता है के साथ अनुभव नहीं कर रहा हूँ सरल मामलों के लिए भी काम नहीं करते हैं। मैंने टॉप-डाउन दृष्टिकोण चुना है। मेरे लिए सभी कोने के मामलों पर विचार करना मुश्किल है। मुझे वास्तव में पता नहीं है कि मैंने सही ढंग से रिकर्सन का आधार चुना है, आदि। मेरा एल्गोरिदम g = h = k = 1, n = 2 (उत्तर 01 + 01 = 10) के लिए सबसे बुनियादी मामले के लिए भी काम नहीं करता है। g = h = k = 1, n = 1 के लिए उत्तर नहीं होना चाहिए लेकिन एल्गोरिदम 1 देता है (जो मूल रूप से 2 के बजाय 1 का उत्पादन करता है)।

int solve(int g, int h, int k, int n, int c = 0) { 
    if (n <= 0) { 
    return 0; 
    } 
    if (dp[g][h][k][n][c]) { 
    return dp[g][h][k][n][c]; 
    } 
    if (!c) { 
    if (g + h == k) { 
     return dp[g][h][k][n][c] = (1 << k) - 1; 
    } 
    int min, a1, a2, a3, a4; 
    min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max(); 
    if (g + h > k && k <= n - 1) { 
     a1 = solve(g, h, k, n - 1, 0); 
    } 
    if (g + h >= k - 1 && k - 1 <= n - 1) { 
     a2 = (1 << (n - 1)) + solve(g, h, k - 1, n - 1, 1); 
    } 
    if (g - 1 + h >= k - 1 && k - 1 <= n - 1) { 
     a3 = (1 << (n - 1)) + solve(g - 1, h, k - 1, n - 1, 0); 
    } 
    if (g + h - 1 >= k - 1 && k - 1 <= n - 1) { 
     a4 = (1 << (n - 1)) + solve(g, h - 1, k - 1, n - 1, 0); 
    } 
    min = std::min({a1, a2, a3, a4}); 
    return dp[g][h][k][n][c] = min; 
    } else { 
    int min, a1, a2, a3, a4; 
    min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max(); 
    if (g - 2 + h >= k && k <= n - 1) { 
     a1 = solve(g - 1, h - 1, k, n - 1, 0); 
    } 
    if (g - 2 + h >= k - 1 && k - 1 <= n - 1) { 
     a2 = (1 << (n - 1)) + solve(g - 1, h - 1, k - 1, n - 1, 1); 
    } 
    if (g - 1 + h >= k && k <= n - 1) { 
     a3 = solve(g - 1, h, k, n - 1, 1); 
    } 
    if (g - 1 + h >= k && k <= n - 1) { 
     a4 = solve(g, h - 1, k, n - 1, 1); 
    } 
    min = std::min({a1, a2, a3, a4}); 
    return dp[g][h][k][n][c] = min; 
    } 
} 
+4

अच्छा सवाल। लेकिन मेरा मानना ​​है कि आप गलत निष्कर्ष (गतिशील प्रोग्रामिंग का उपयोग करके) के लिए बहुत तेजी से कूदते हैं। मैं एक और रचनात्मक दृष्टिकोण की तलाश में हूं। कुछ मामलों को हल करके, 1 <= k, g, h <= 3, हाथ से, आप एक पैटर्न देख सकते हैं। नाइटपिक: "इस तरह के पूर्णांक का अधिकतम मूल्य' 2^(एन + 1) - 1' "है - यह वास्तव में' 2^n - 1' है। – Gassa

+0

@ गासा। यदि आप संकेत दे रहे हैं कि जी + एच = के + 1 के लिए समाधान 10 + के हैं, तो जी + एच = के + 2 के लिए यह 110 + के हैं और इसी तरह, आप गलत हैं। सबसे पहले, जी + एच - के> के लिए थोड़ा अधिक कॉम्प्लेक्स पैटर्न है। दूसरा, दोनों में गिनती है! – Atin

+1

क्षमा करें, मेरे पास दिमाग में एक विशिष्ट पैटर्न नहीं है। इसके बजाय, एक सामान्य जांच विधि जो पैटर्न - या इसके अस्तित्व को प्रकट करेगी, अगर वास्तव में यह मामला है। – Gassa

उत्तर

4

आप किसी भी गतिशील प्रोग्रामिंग के बिना बिट गिनती जी, एच, और के आधार पर सबसे छोटी राशि का निर्माण कर सकते हैं।यह मानते हुए कि जी ≥ घंटा (उन्हें अन्यथा स्विच) इन नियम हैं:

कश्मीर ≤ ज ≤ जी

 11111111 <- g ones 
    111100000111 <- h-k ones + g-k zeros + k ones 
1000000000110 <- n must be at least h+g-k+1 

ज ≤ कश्मीर ≤ जी

1111111111 <- g ones 
     11111100 <- h ones + k-h zeros 
    1011111011 <- n must be at least g+1 

ज ≤ जी ≤ कश्मीर

1111111100000 <- g ones + k-g ones 
1100000011111 <- g+h-k ones, k-h zeros, k-g ones 
11011111111111 <- n must be at least k+1, or k if g+h=k 

उदाहरण:

k=1   k=2   k=3   k=4  
0000111111 0000111111 0000111111 0000111111 
0111000001 0011000011 0001000111 0000001111 
---------- ---------- ---------- ---------- 
1000000000 0100000010 0010000110 0001001110 
k=4   k=5   k=6 
0000111111 0000111111 0000111111 
0000001111 0000011110 0000111100 
---------- ---------- ---------- 
0001001110 0001011101 0001111011 
k=6   k=7   k=8   k=9   k=10 
0000111111 0001111110 0011111100 0111111000 1111110000 
0000111100 0001110001 0011000011 0100000111 0000001111 
---------- ---------- ---------- ---------- ---------- 
0001111011 0011101111 0110111111 1011111111 1111111111 

या, सीधे जा रहा: एन = 10, जी = 6 और ज = 4 के लिए कश्मीर के सभी मानों ए और बी की गणना किए बिना सी के मूल्य के लिए:

कश्मीर ≤ ज ≤ जी

c = (1 << (g + h - k)) + ((1 << k) - 2) 

ज ≤ कश्मीर ≤ जी

c = (1 << g) + ((1 << k) - 1) - (1 << (k - h)) 

ज ≤ जी ≤ कश्मीर

c = ((1 << (k + 1)) - 1) - (1 << ((g - h) + 2 * (k - g))) 

ज + g = k

c = (1 << k) - 1 

जो इस निराश के साथ सांसारिक कोड में जो परिणाम:

int smallest_sum(unsigned n, unsigned g, unsigned h, unsigned k) { 
    if (g < h) {unsigned swap = g; g = h; h = swap;} 
    if (k == 0) return (g > 0 || h > 0 || n < 1) ? -1 : 0; 
    if (h == 0) return (g != k || n < k) ? -1 : (1 << k) - 1; 
    if (k <= h) return (n <= h + g - k) ? -1 : (1 << (g + h - k)) + ((1 << k) - 2); 
    if (k <= g) return (n <= g) ? -1 : (1 << g) + ((1 << k) - 1) - (1 << (k - h)); 
    if (k < g + h) return (n <= k) ? -1 : (1 << (k + 1)) - 1 - (1 << (2 * k - g - h)); 
    if (k == g + h) return (n < k) ? -1 : (1 << k) - 1; 
    return -1; 
} 

कुछ उदाहरण परिणाम:

n=31, g=15, h=25, k=10 -> 1,073,742,846 (1000000000000000000001111111110) 
n=31, g=15, h=25, k=20 ->  34,602,975 (0000010000011111111111111011111) 
n=31, g=15, h=25, k=30 -> 2,146,435,071 (1111111111011111111111111111111) 

(मैं परिणाम की तुलना के साथ एन, जी, एच और के प्रत्येक मूल्य के लिए 0 से 20 तक ची के लिए एक ब्रूट-बल एल्गोरिदम के सीके शुद्धता, और कोई मतभेद नहीं मिला।)

2

मैं गतिशील प्रोग्रामिंग दृष्टिकोण के बारे में भी यकीन नहीं: तो, यहाँ मेरी भयंकर कोड (केवल मूलभूत सी ++) चला जाता है। अगर मैं सही ढंग से समझता हूं, तो आपको dp[g + 1][h][k][n], dp[g][h + 1][k][n], dp[g][h][k + 1][n] और dp[g][h][k][n + 1] पर जाने के लिए परिभाषित करने की आवश्यकता होगी, पिछले कंप्यूटेशंस के कार्य में, लेयर बिट के साथ और बिना, और मुझे यकीन नहीं है कि सभी के लिए सही नियम क्या हैं उन।

मुझे लगता है कि समस्या के बारे में सोचने का एक आसान तरीका A* search पेड़ के रूप में है, जहां प्रत्येक नोड में दो आंशिक उम्मीदवार संख्याएं शामिल होती हैं, चलिए उन्हें जी और एच कहते हैं। आप जी = 0 और एच = 0 स्तर एम = 0 पर, और निम्नानुसार कार्य करें:

  1. यदि जी + एच में एन या कम बिट्स और के 1 बिट्स हैं, तो यह समाधान है, आपको यह मिला!
  2. अन्यथा, यदि
    n - मीटर जी + एच में 1 बिट्स की < संख्या - k
    नोड (कोई संभव समाधान) त्यागें।
  3. अन्यथा, यदि
    (छ + ज) - < कश्मीर (एच 1 में बिट्स की जी + संख्या में 1 बिट्स की संख्या) - जी + एच में 1 बिट्स की संख्या
    नोड त्यागने (नहीं व्यवहार्य उम्मीदवारों) ।
  4. अन्यथा, नोड को एक नए स्तर पर शाखा करें। आम तौर पर आप प्रत्येक नोड के चार बच्चों को बनाते हैं, जी और एच को क्रमश: 0 और 0, 0 और 1, 1 और 0 या 1 और 1 के साथ उपसर्ग करते हैं। हालांकि:
    • यदि जी में 1 बिट्स की संख्या जी से कम है, और इसी तरह एच और एच के लिए आप केवल 1 के साथ जी से पहले हो सकते हैं। मीटर> g - - 1 बिट्स की संख्या जी
      में एच और ज के लिए और इसी तरह
    • स्तर मीटर (जी और एच एम बिट्स है), आप केवल जी के साथ एक 0 यदि
      n पूर्व में होना कर सकते हैं।
    • यदि जी == एच और जी == एच, तो आप 0 और 1 और 1 और 0 में से एक को छोड़ सकते हैं, क्योंकि वे एक ही उप-चीज का नेतृत्व करेंगे।
  5. अगला नोड जारी रखें और जब तक आपको कोई समाधान न मिल जाए तब तक दोहराएं या आपके पास जाने के लिए कोई और नोड्स न हो।

जिस क्रम में आप नोड्स पर जाते हैं वह महत्वपूर्ण है। आपको नोड्स को प्राथमिकता कतार/ढेर में स्टोर करना चाहिए जैसे कि अगला नोड हमेशा पहला नोड होता है जो संभावित रूप से सर्वोत्तम समाधान का कारण बन सकता है। यह वास्तव में आसान है, आपको केवल प्रत्येक नोड जी + एच के लिए लेने की आवश्यकता है और इसे तक पहुंचने के लिए 1 बिट्स की आवश्यक संख्या के साथ उपसर्ग करना है; यह वहां से सबसे अच्छा संभव समाधान है।

अवैध नोड्स (चरण 2 और 3) को त्यागने के लिए संभवतः बेहतर नियम हैं, लेकिन एल्गोरिदम का विचार समान है।

+0

धन्यवाद, विचार बहुत अच्छा है। हालांकि, मैं वास्तव में समझ नहीं पा रहा हूं कि 'ए * -नेस' को कैसे कार्यान्वित किया जाए। प्राथमिकता कतार, अर्थात् किनारे के वजन (संभवतः सभी किनारों के लिए = 1) और हेरिस्टिक वजन के लिए चाबियाँ क्या होनी चाहिए। 1-बिट्स की आवश्यक संख्या के साथ उपसर्ग करना संख्या देगा, लेकिन इस बात की कोई गारंटी नहीं है कि यह जी, एच 1-बिट्स के साथ दो पूर्णांक का योग है। इसके अलावा, प्राथमिकता कतार/ढेर के लिए इस तरह के उपसर्ग की भूमिका अस्पष्ट लगती है – Atin

+1

@ एटिन मिनी-ढेर के लिए वजन पूर्ववर्ती मान होगा। जैसा कि आपने कहा था, इस बात की कोई गारंटी नहीं है कि आप किसी दिए गए नोड से उस नंबर तक पहुंचने में सक्षम होंगे, लेकिन आपको गारंटी है कि आप संभवतः एक बेहतर समाधान तक पहुंच नहीं पाएंगे (यानी, यह एक आशावादी ह्युरिस्टिक है), जो कि है ए * को काम करने की आवश्यकता है (जाहिर है, आशावादी ह्युरिस्टिक जितना बेहतर होगा)। – jdehesa

+0

ओह, मैं देखता हूं। हालांकि, यह दृष्टिकोण ए * खोज के बजाय इसे लालची सर्वश्रेष्ठ-पहली खोज बनाने वाले किनारे के वजन को उपेक्षा करता है। किनारे के भार अंतर्निहित हैं या वास्तव में यह सबसे अच्छी खोज है? बस यह सुनिश्चित करना कि मैं सब कुछ सही ढंग से समझ गया। @jdehesa – Atin

संबंधित मुद्दे

 संबंधित मुद्दे