प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. समस्या

भवद्भ्यः केवलं सकारात्मकपूर्णाङ्काः समाविष्टाः अरिक्ताः सरणी nums दत्ताः सन्ति । कृपया न्याययन्तु यत् एतत् सरणी द्वयोः उपसमूहयोः विभक्तुं शक्यते वा येन उपसमूहद्वयस्य तत्त्वानां योगः समानः भवति ।

2. समाधानविचारः 1

गतिशील प्रोग्रामिंग समाधान

बैकट्रैकिंग् एल्गोरिदम् इत्यस्य उपयोगेन एषा समस्या समाधानं कर्तुं न शक्यते यदि दत्तांशस्य परिमाणं बृहत् भवति तर्हि तस्य समयः समाप्तः भविष्यति । वयं डायनामिक प्रोग्रामिंग् इत्यस्य उपयोगं कर्तुं शक्नुमः ।
अस्मिन् प्रश्ने निर्धारितं भवति यत् सङ्ग्रहस्य द्वयोः भागयोः विभक्तौ भागद्वयस्य तत्त्वानां योगः समानः भवति वा इति । प्रथमं अस्माभिः सरणीयां सर्वेषां तत्त्वानां योगं गणनीयं, ततः योगः समसङ्ख्या अस्ति वा इति निर्धारयितुं आवश्यकम्: यदि सा समसङ्ख्या नास्ति तर्हि तस्य अर्थः अस्ति यत् सा पूर्णतया समानभागद्वये विभक्तुं न शक्यते, पुनः आगमिष्यति च मिथ्या साक्षात् ।
यदि समसङ्ख्या अस्ति तर्हि अस्माभिः केवलं निर्धारयितव्यं यत् केचन तत्त्वानि सन्ति येषां योगः योग/2 इत्यस्य समः अस्ति तर्हि शेषः अपि योग/2 इत्यस्य समः भवितुमर्हति, यस्य अर्थः अस्ति वयं समानतत्त्वैः सह सरणीं द्वयोः भागयोः विभक्तुं शक्नुमः ।
तदा समस्या अस्मिन् समये अतीव स्पष्टा अस्ति /2, अस्य अर्थः अस्ति यत् वयं Divide इति सरणीं समानभागद्वये स्थापयितुं शक्नुमः । किं एषा क्लासिक 0-1 knapsack समस्या नास्ति? नैपसैकसमस्यानां श्रृङ्खलायां मूलभूतं नैपसैकसमस्या विस्तरेण अधः पठितुं शक्यते अहम् अत्र परिचयं पुनः न करिष्यामि। वयं तस्य पुनरावृत्तिसूत्रं अन्विष्य dp[i][j] परिभाषयामः यत् i-तमं द्रव्यं j क्षमतायुक्ते बैकपैक् मध्ये स्थापयित्वा प्राप्तं अधिकतमं मूल्यं प्रतिनिधियति ।
i-तमस्य द्रव्यस्य मूल्यं nums [i -1] अस्ति:
यदि nums [i -1]>j, तर्हि तस्य अर्थः अस्ति यत् backpack क्षमता पर्याप्तं नास्ति तथा च i-th item स्थापयितुं न शक्यते, अतः वयं i-th item इत्यस्य चयनं कर्तुं न शक्नुमः, तर्हि
dp[i][j]=dp[i -1][j];
यदि nums [i -1]<=j तर्हि तस्य अर्थः अस्ति यत् jth द्रव्यं पृष्ठपुटे स्थापयितुं शक्यते, केवलं अधिकतमं मूल्यं गृह्णीमः यदि वयं तत् स्थापयामः backpack capacity अधिकतमं मूल्यं हाँ
dp[i][j]=dp[i-1][ज-नुम्स[i-1]]+nums[i-1]
यदि त्वं न मुञ्चसि
dp[i][j]=dp[i -1][j];
द्वयोः अधिकतमं गृह्यताम्

अन्तिमः पुनरावर्तनीयः सूत्रः कोडः च निम्नलिखितरूपेण सन्ति ।

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<int>> dp(length + 1, std::vector<int>(target + 1, 0));
    for (int i = 1; i <= length; ++i) {
        for (int j = 1; j <= target; ++j) {
            // 下面是递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 判断背包最大是否能存放和为target的元素
    return dp[length][target] == target;
}

वयम् अपि एवं लिखितुं शक्नुमः । 0]=true, यस्य अर्थः प्रथमाः 0 तत्त्वानि (अर्थात् कोऽपि तत्त्वः नास्ति) 0 इत्यस्य योगं निर्मातुम् अर्हति ।code show यथा अधः

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<bool>> dp(length + 1, std::vector<bool>(target + 1, false));
    // base case
    dp[0][0] = true;
    for (int i = 1; i <= length; ++i) {
        for (int j = 0; j <= target; ++j) {
            // 递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 返回能否找到和为target的子集
    return dp[length][target];
}

वयं पश्यामः यत् उपरिष्टात् द्वि-आयामी-सरण्याः गणनायां वर्तमान-मूल्यं केवलं उपरिष्टात् पङ्क्तौ एव सम्बद्धं भवति, अतः वयं तत् एक-आयामी-रूपेण परिवर्तयितुं शक्नुमः, ध्यानं कुर्वन्तु यत् द्वितीयं for लूप् फ्लैशबैक् भवितुमर्हति, अन्यथा पूर्वमूल्यं अधिलिखितं भविष्यति तथा परिणामः गलतः भविष्यति , समीपतः अवलोकयन्तु
dp[j] = (dp[j] || dp[j - nums [i - 1]]);
भवन्तः अवगन्तुं शक्नुवन्ति यत् समानपङ्क्तौ अन्ते स्थितं मूल्यं पूर्वस्य उपरि आश्रितं भवति यदि तत् फ्लैशबैक् न भवति तर्हि पूर्वमूल्यं परिवर्तितं भवति, येन परवर्तीयाः गणनायां दोषः भविष्यतिकोडं अवलोकयामः

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<bool> dp(target + 1, false);
    // base case
    dp[0] = true;
    for (int i = 0; i < length; ++i) {
        // 注意这里j要倒序
        for (int j = target; j >= nums[i]; --j) {
            // 递推公式
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    // 返回能否找到和为target的子集
    return dp[target];
}

3. समाधानविचारः 2

DFS एल्गोरिदम समाधान

प्रत्येकं तत्त्वं चयनं कर्तुं शक्यते वा न वा भवद्भिः केवलं निर्धारयितुं आवश्यकं यत् तस्य सर्वेषु सम्भाव्यसंयोजनेषु तत्त्वानां योगः योगः/2 इत्यस्य बराबरः अस्ति वामबालनोड् इत्यस्य चयनं प्रतिनिधियति वर्तमानतत्त्वं, तथा च दक्षिणः बालनोड् वर्तमानतत्त्वस्य चयनं प्रतिनिधियति बालनोड् वर्तमानतत्त्वं न चयनितम् इति सूचयति, यथा अधोलिखिते चित्रे दर्शितं नारङ्गवर्णीयः नोडः वर्तमानतत्त्वस्य चयनं भवति इति सूचयति वर्तमानतत्त्वं न चयनितम् इति सूचयति ।

प्रथमं प्रारम्भिकं कार्यान्वयनसङ्केतं अवलोकयामः

#include <vector>
 
bool dfs(const std::vector<int>& nums, int target, int index) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index == nums.size() || target < 0) return false;
    // 选择当前元素和不选择当前元素两种情况
    return dfs(nums, target - nums[index], index + 1) || dfs(nums, target, index + 1);
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) return false;
    // 调用dfs函数
    return dfs(nums, sum >> 1, 0);
}

परन्तु दुर्भाग्येन गणनायाः परिमाणम् अतिबृहत् इति कारणतः ऑपरेशनस्य समयः समाप्तः भविष्यति वयं तत् अनुकूलितुं शक्नुमः तथा च कोडं अवलोकयितुं शक्नुमः ।

#include <vector>
 
bool dfs(const std::vector<int>& nums, int index, int target, std::vector<std::vector<int>>& map) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index >= nums.size() || target < 0) return false;
    // 如果此子问题已经被计算过，直接返回结果
    if (map[index][target] != -1) return map[index][target] == 1;
    // 选择当前元素
    bool select = dfs(nums, index + 1, target - nums[index], map);
    // 不选择当前元素
    bool unSelect = dfs(nums, index + 1, target, map);
    // 存储结果，并返回
    map[index][target] = select || unSelect ? 1 : 0;
    return select || unSelect;
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if (sum % 2 != 0) return false;
    // sum除以2
    int target = sum / 2;
    std::vector<std::vector<int>> map(nums.size(), std::vector<int>(target + 1, -1));
    return dfs(nums, 0, target, map);
}

4. समाधानविचारः 3

बिट ऑपरेशन समाधान

अत्र बिट्-क्रियाणां उपयोगः कर्तुं शक्यते, परन्तु कुञ्जी प्रश्ने केषुचित् प्रतिबन्धेषु निहितं भवति, यथा सकारात्मकपूर्णाङ्कानां अ-रिक्त-सरणिः, प्रत्येकस्मिन् सरणीयां तत्त्वानि १०० तः अधिकाः न भविष्यन्ति, सरणीयाः आकारः २०० तः अधिकः न भविष्यति इत्यादि .
सिद्धान्तः अतीव सरलः अस्ति अस्माकं केवलं sum+1 आकारस्य array bits[sum+1] इत्यस्य कृते आवेदनं कर्तव्यम् अस्ति int and The long type अतीव लघु अस्ति, वयम् अत्र array इत्यस्य उपयोगं कुर्मः । ततः प्रत्येकं समये सरणीयां कश्चन तत्त्वः, यथा m, भ्रमितः भवति, तदा द्विचक्रीयबिट् m बिट् द्वारा वामभागे स्थानान्तरितः भवति ततः मूलद्विचक्रीयबिट् इत्यनेन सह OR भवति । अन्ते bits[sum/2] 1 अस्ति वा इति निर्धारयन्तु, यदि 1 अस्ति तर्हि true प्रेषयन्तु ।पाठविवरणं बहु ऋजुं नास्ति ।

अन्ते, भवान् एकं नियमं प्राप्स्यति, अर्थात् यावत् अन्तिमः ऑपरेशन परिणामः 1 भवति, तावत् यावत् सः सरणीयां तत्त्वानां उपयोगेन संयोजितुं शक्यते, तावत् यावत् एतत् सरणीयां तत्त्वानां उपयोगेन संयोजितुं न शक्यते above process. , कोडः लिखितुं सुलभः अस्ति। यतः अस्माभिः केवलं निर्धारयितुं आवश्यकं यत् द्विचक्रीयबिट् मध्ये मध्यमं मूल्यं 1 अस्ति वा, अस्माकं केवलं निम्नबिट् गणना करणीयम्, उच्चबिट् इत्यस्य गणना सर्वथा आवश्यकं नास्ति, यतः तत् वामभागे स्थापितं भवति, उच्चं च bit इत्यस्य मध्यमूल्ये किमपि प्रभावः न भविष्यति, अतः वयम् अत्र किञ्चित् अनुकूलनं कर्तुं शक्नुमः, अन्ते च कोडं पश्यामः ।

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有数字的和
    int sum = 0;
    for (int n : nums) {
        sum += n;
    }
    // 如果sum是奇数，直接返回false
    if ((sum & 1) == 1) {
        return false;
    }
    int len = sum / 2;
    // 这里bits的长度是len+1，因为我们只需要计算低位就行了，没必要计算所有的
    std::vector<char> bits(len + 1, 0);
    bits[0] = 1;
    for (int num : nums) {
        for (int j = len - num; j >= 0; j--) {
            bits[j + num] |= bits[j];
        }
        // 判断中位数如果是1，说明可以分成两种相等的子集，直接返回true，不需要再计算了
        if ((bits[len] & 1) != 0) {
            return true;
        }
    }
    return false;
}