पुराना शीर्ष कोडर पहेली: +

Question

डालने से एक संख्या बनाना मैं this topcoder problem के बारे में सोच रहा हूं।

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

उदाहरण के लिए, "303" और 6 का लक्ष्य योग मानें। सर्वोत्तम रणनीति "3 + 03" है।

मैं इसे जानवर बल के साथ हल के रूप में निम्नानुसार हैं:

for each i in 0 to 9 // i -- number of plus signs to insert 
    for each combination c of i from 10 
    for each pos in c // we can just split the string w/o inserting plus signs 
     insert plus sign in position pos 
    evaluate the expression 
    if the expression value == given sum 
     return i 

यह मतलब है? क्या यह प्रदर्शन बिंदु से इष्टतम है?

...

खैर, अब मुझे लगता है कि एक गतिशील प्रोग्रामिंग समाधान और अधिक कुशल हो जाएगा। हालांकि यह दिलचस्प है अगर प्रस्तुत समाधान वैसे भी समझ में आता है।

Answer 1

यह निश्चित रूप से इष्टतम नहीं है। यदि, उदाहरण के लिए, आपको "1234567890" स्ट्रिंग दी गई है और लक्ष्य तीन अंकों वाला नंबर है, तो आप जानते हैं कि आपको स्ट्रिंग को कम से कम चार भागों में विभाजित करना है, इसलिए आपको 0, 1, या 2 प्रविष्टियों की जांच करने की आवश्यकता नहीं है । इसके अलावा, लक्ष्य स्वीकार्य सम्मिलन पदों की सीमा को सीमित करता है। दोनों बिंदुओं के छोटे तारों के लिए छोटे प्रभाव पड़ते हैं, लेकिन लंबे समय तक एक बड़ा अंतर बना सकते हैं। हालांकि, मुझे संदेह है कि एक बहुत ही बेहतर विधि है, थोड़ा डीपी गंध करता है।

Answer 2

क्योंकि इनपुट लंबाई छोटी है (10) सभी संभावित तरीकों (जिसे लंबाई 10 के साधारण बाइनरी काउंटर द्वारा पाया जा सकता है) छोटा है (2^10 = 1024), इसलिए आपका एल्गोरिदम पर्याप्त तेज़ है और वैध परिणाम देता है, और आईएमओ में इसे सुधारने की कोई जरूरत नहीं है।

जब तक आपका समाधान समय और स्मृति और अन्य दिए गए बाधाओं में ठीक काम नहीं करता है, तब तक माइक्रो ऑप्टिमाइज़ेशन करने की आवश्यकता नहीं होती है। उदाहरण के लिए इस मामले को अक्कप्पा के रूप में दो-विभाजन समस्या में डीपी जैसे डीपी के साथ हल किया जा सकता है, लेकिन जब आपका एल्गोरिदम तेजी से होता है तो ऐसा करने की कोई आवश्यकता नहीं होती है और कुछ बड़े स्थिरता या कोड को पढ़ने योग्य नहीं हो सकता है।

मैं बहुत स्ट्रिंग पार्सिंग से बचने के लिए स्ट्रिंग एक बार (लंबाई 10 की सरणी में) के पार्स अंक प्रदान करता हूं, और केवल * 10^के + का उपयोग करता हूं ... (इसके अलावा आप 10^के के लिए गणना कर सकते हैं = 0..9 स्टार्टअप में और इसके मूल्य को सहेजें)।

Answer 3

मैंने इसे अभी तक बहुत अधिक विचार नहीं दिया है, लेकिन यदि आप नीचे स्क्रॉल करते हैं तो आप प्रतियोगिता से लिंक देख सकते हैं, और वहां से आप सॉल्वर के समाधान देख सकते हैं। यहां सी # में एक है।

using System; 
using System.Text; 
using System.Text.RegularExpressions; 
using System.Collections; 

public class QuickSums { 
    public int minSums(string numbers, int sum) { 
     int[] arr = new int[numbers.Length]; 
    for (int i = 0 ; i < arr.Length; i++)  
     arr[i] = 0; 

    int min = 15; 

    while (arr[arr.Length - 1] != 2)  
    { 
     arr[0]++; 
     for (int i = 0; i < arr.Length - 1; i++) 
     if (arr[i] == 2) 
     { 
      arr[i] = 0; 
      arr[i + 1]++; 
     } 

     String newString = ""; 
     for (int i = 0; i < numbers.Length; i++) 
     { 
     newString+=numbers[i]; 
     if (arr[i] == 1) 
      newString+="+"; 
     } 

     String[] nums = newString.Split('+'); 
     int sum1 = 0; 
     for (int i = 0; i < nums.Length; i++) 
     try 
     { 
      sum1 += Int32.Parse(nums[i]); 
     } 
     catch 
     { 
     } 

     if (sum == sum1 && nums.Length - 1 < min) 
     min = nums.Length - 1; 
    } 

    if (min == 15) 
     return -1; 

    return min; 
    } 

} 

Answer 4

मुझे लगता है कि समस्या मैट्रिक्स चेन गुणात्मक समस्या के समान है जहां हमें कम से कम गुणा के लिए ब्रेसिज़ रखना होगा। यहां ब्रेसिज़ '+' का प्रतिनिधित्व करते हैं। तो मुझे लगता है कि इसे समान डीपी दृष्टिकोण से हल किया जा सकता है .. इसे लागू करने का प्रयास करेंगे।

Answer 5

गतिशील प्रोग्रामिंग:

public class QuickSums { 

public static int req(int n, int[] digits, int sum) { 

    if (n == 0) { 
     if (sum == 0) 
      return 0; 
     else 
      return -1; 
    } else if (n == 1) { 
     if (sum == digits[0]) { 
      return 0; 
     } else { 
      return -1; 
     } 
    } 

    int deg = 1; 
    int red = 0; 

    int opt = 100000; 
    int split = -1; 

    for (int i=0; i<n;i++) { 
     red += digits[n-i-1] * deg; 

     int t = req(n-i-1,digits,sum - red); 
     if (t != -1 && t <= opt) { 
      opt = t; 
      split = i; 
     } 
     deg = deg*10; 
    } 

    if (opt == 100000) 
     return -1; 
    if (split == n-1) 
     return opt; 
    else 
     return opt + 1; 

} 

public static int solve (String digits,int sum) { 
    int [] dig = new int[digits.length()]; 
    for (int i=0;i<digits.length();i++) { 
     dig[i] = digits.charAt(i) - 48; 
    } 

    return req(digits.length(), dig, sum); 
} 


public static void doit() { 
    String digits = "9230560001"; 
    int sum = 71; 

    int result = solve(digits, sum); 
    System.out.println(result); 
} 

Answer 6

बहुत देर हो चुकी हो करने के लिए लगता है .. लेकिन सिर्फ कुछ टिप्पणियों और जवाब यहां जो कोई दृष्टिकोण डीपी को कहते हैं पढ़ें।

सार पाने के लिए:: लेकिन यह एक बहुत ही सरल रॉड काटने समस्या के लिए इसी तरह डी पी है

int val[N][N]; 
int dp[N][T]; 

val[i][j]: numerical value of s[i..j] including both i and j 

val[i][j] can be easily computed using dynamic programming approach in O(N^2) time 

dp[i][j] : Minimum no of '+' symbols to be inserted in s[0..i] to get the required sum j 

dp[i][j] = min(1+dp[k][j-val[k+1][j]]) over all k such that 0<=k<=i and val[k][j]>0 

सरल शब्दों में, डी पी की गणना करने के [मैं] [जे] क्या आप पिछले की स्थिति कश्मीर मान '+' प्रतीक और फिर एस [0..k]