」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > 子集和問題的 PHP 程式

子集和問題的 PHP 程式

發佈於2024-11-07
瀏覽:989

PHP Program for Subset Sum Problem

子集和問題是電腦科學和動態規劃中的經典問題。給定一組正整數和一個目標和,任務是確定是否存在給定集合的子集,其元素總和等於目標和。

子集與問題的PHP程序

使用遞歸解決方案

例子

 $sum)
      return isSubsetSum($set, $n - 1, $sum);
   // Check if the sum can be obtained by either including or excluding the last element
   return isSubsetSum($set, $n - 1, $sum) ||
      isSubsetSum($set, $n - 1, $sum - $set[$n - 1]);
}
// Driver Code
$set = array(1, 7, 4, 9, 2);
$sum = 16;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
   echo "Found a subset with the given sum
"; else echo "No subset with the given sum
"; $sum = 25; $n = count($set); if (isSubsetSum($set, $n, $sum) == true) echo "Found a subset with the given sum."; else echo "No subset with the given sum."; ?>

輸出

Found a subset with the given sum.
No subset with the given sum.

在提供的範例中,集合為 [1, 7, 4, 9, 2],目標和為 16 和 25。目標和為 25 的第二次呼叫傳回 false,表示不存在子集加起來為 25。因此輸出為 Found a subset with the給定 sum in first call。第二次呼叫中沒有給定總和的子集。

使用動態規劃的偽多項式時間

例子

= $set[$i-1])
				$subset[$i][$j] =
					$subset[$i-1][$j] ||
					$subset[$i - 1][$j -
							$set[$i-1]];
		}
	}
	/* // uncomment this code to print table
	for (int i = 0; i 

輸出

Found a subset with given sum.

在提供的範例中,集合為 [8, 15, 26, 35, 42, 59],目標和為 50。 函數呼叫isSubsetSum($set, $ n, $sum) 傳回true,表示集合中存在子集[8, 42],其總和為50 。因此,程式碼的輸出為找到具有給定總和的子集。

結論

總之,有兩種不同的方法來解決子集和問題。第一個解決方案是遞歸方法,檢查給定集合中是否存在總和等於目標總和的子集。它利用回溯來探索所有可能的組合。然而,該解決方案在最壞的情況下可能具有指數時間複雜度。

第二種解決方案利用動態規劃並以自下而上的方式解決子集和問題。它構造一個表來儲存中間結果,並有效地確定是否存在具有給定總和的子集。這種方法的時間複雜度為 O(n*sum),比遞歸解決方案更有效。這兩種方法都可以用來解決子集和問題,動態規劃解決方案對於較大的輸入更有效。

版本聲明 本文轉載於:https://www.tutorialspoint.com/php-program-for-subset-sum-problem如有侵犯,請聯絡[email protected]刪除
最新教學 更多>
  • 在PHP中如何高效檢測空數組?
    在PHP中如何高效檢測空數組?
    在PHP 中檢查一個空數組可以通過各種方法在PHP中確定一個空數組。如果需要驗證任何數組元素的存在,則PHP的鬆散鍵入允許對數組本身進行直接評估:一種更嚴格的方法涉及使用count()函數: if(count(count($ playerList)=== 0){ //列表為空。 } 對...
    程式設計 發佈於2025-04-26
  • 在Ubuntu/linux上安裝mysql-python時,如何修復\“ mysql_config \”錯誤?
    在Ubuntu/linux上安裝mysql-python時,如何修復\“ mysql_config \”錯誤?
    mysql-python安裝錯誤:“ mysql_config找不到”“ 由於缺少MySQL開發庫而出現此錯誤。解決此問題,建議在Ubuntu上使用該分發的存儲庫。使用以下命令安裝Python-MysqldB: sudo apt-get安裝python-mysqldb sudo pip in...
    程式設計 發佈於2025-04-26
  • 如何有效地轉換PHP中的時區?
    如何有效地轉換PHP中的時區?
    在PHP 利用dateTime對象和functions DateTime對象及其相應的功能別名為時區轉換提供方便的方法。例如: //定義用戶的時區 date_default_timezone_set('歐洲/倫敦'); //創建DateTime對象 $ dateTime = ne...
    程式設計 發佈於2025-04-26
  • 為什麼不````''{margin:0; }`始終刪除CSS中的最高邊距?
    為什麼不````''{margin:0; }`始終刪除CSS中的最高邊距?
    在CSS 問題:不正確的代碼: 全球範圍將所有餘量重置為零,如提供的代碼所建議的,可能會導致意外的副作用。解決特定的保證金問題是更建議的。 例如,在提供的示例中,將以下代碼添加到CSS中,將解決餘量問題: body H1 { 保證金頂:-40px; } 此方法更精確,避免了由全局保證金重置...
    程式設計 發佈於2025-04-26
  • 如何從PHP中的數組中提取隨機元素?
    如何從PHP中的數組中提取隨機元素?
    從陣列中的隨機選擇,可以輕鬆從數組中獲取隨機項目。考慮以下數組:; 從此數組中檢索一個隨機項目,利用array_rand( array_rand()函數從數組返回一個隨機鍵。通過將$項目數組索引使用此鍵,我們可以從數組中訪問一個隨機元素。這種方法為選擇隨機項目提供了一種直接且可靠的方法。
    程式設計 發佈於2025-04-26
  • 如何在鼠標單擊時編程選擇DIV中的所有文本?
    如何在鼠標單擊時編程選擇DIV中的所有文本?
    在鼠標上選擇div文本單擊帶有文本內容,用戶如何使用單個鼠標單擊單擊div中的整個文本?這允許用戶輕鬆拖放所選的文本或直接複製它。 在單個鼠標上單擊的div元素中選擇文本,您可以使用以下Javascript函數: function selecttext(canduterid){ if(d...
    程式設計 發佈於2025-04-26
  • C++20 Consteval函數中模板參數能否依賴於函數參數?
    C++20 Consteval函數中模板參數能否依賴於函數參數?
    [ consteval函數和模板參數依賴於函數參數在C 17中,模板參數不能依賴一個函數參數,因為編譯器仍然需要對非contexexpr futcoriations contim at contexpr function進行評估。 compile time。 C 20引入恆定函數,必須在編譯時進...
    程式設計 發佈於2025-04-26
  • 在JavaScript中如何獲取實際渲染的字體,當CSS字體屬性未定義時?
    在JavaScript中如何獲取實際渲染的字體,當CSS字體屬性未定義時?
    Accessing Actual Rendered Font when Undefined in CSSWhen accessing the font properties of an element, the JavaScript object.style.fontFamily and objec...
    程式設計 發佈於2025-04-26
  • 如何在Java字符串中有效替換多個子字符串?
    如何在Java字符串中有效替換多個子字符串?
    在java 中有效地替換多個substring,需要在需要替換一個字符串中的多個substring的情況下,很容易求助於重複應用字符串的刺激力量。 However, this can be inefficient for large strings or when working with nu...
    程式設計 發佈於2025-04-26
  • 為什麼我在Silverlight Linq查詢中獲得“無法找到查詢模式的實現”錯誤?
    為什麼我在Silverlight Linq查詢中獲得“無法找到查詢模式的實現”錯誤?
    查詢模式實現缺失:解決“無法找到”錯誤在Silverlight應用程序中,嘗試使用LINQ建立LINQ連接以錯誤而實現的數據庫”,無法找到查詢模式的實現。”當省略LINQ名稱空間或查詢類型缺少IEnumerable 實現時,通常會發生此錯誤。 解決問題來驗證該類型的質量是至關重要的。在此特定實例...
    程式設計 發佈於2025-04-26
  • 如何使用Python理解有效地創建字典?
    如何使用Python理解有效地創建字典?
    在python中,詞典綜合提供了一種生成新詞典的簡潔方法。儘管它們與列表綜合相似,但存在一些顯著差異。 與問題所暗示的不同,您無法為鑰匙創建字典理解。您必須明確指定鍵和值。 For example:d = {n: n**2 for n in range(5)}This creates a dict...
    程式設計 發佈於2025-04-26
  • 為什麼PYTZ最初顯示出意外的時區偏移?
    為什麼PYTZ最初顯示出意外的時區偏移?
    與pytz 最初從pytz獲得特定的偏移。例如,亞洲/hong_kong最初顯示一個七個小時37分鐘的偏移: 差異源利用本地化將時區分配給日期,使用了適當的時區名稱和偏移量。但是,直接使用DateTime構造器分配時區不允許進行正確的調整。 example pytz.timezone(&#...
    程式設計 發佈於2025-04-26
  • 如何限制動態大小的父元素中元素的滾動範圍?
    如何限制動態大小的父元素中元素的滾動範圍?
    在交互式接口中實現垂直滾動元素的CSS高度限制問題:考慮一個佈局,其中我們具有與用戶垂直滾動一起移動的可滾動地圖div,同時與固定的固定sidebar保持一致。但是,地圖的滾動無限期擴展,超過了視口的高度,阻止用戶訪問頁面頁腳。 $("#map").css({ margin...
    程式設計 發佈於2025-04-26
  • Python讀取CSV文件UnicodeDecodeError終極解決方法
    Python讀取CSV文件UnicodeDecodeError終極解決方法
    在試圖使用已內置的CSV模塊讀取Python中時,CSV文件中的Unicode Decode Decode Decode Decode decode Error讀取,您可能會遇到錯誤的錯誤:無法解碼字節 在位置2-3中:截斷\ uxxxxxxxx逃脫當CSV文件包含特殊字符或Unicode的路徑逃...
    程式設計 發佈於2025-04-26
  • Go語言垃圾回收如何處理切片內存?
    Go語言垃圾回收如何處理切片內存?
    Garbage Collection in Go Slices: A Detailed AnalysisIn Go, a slice is a dynamic array that references an underlying array.使用切片時,了解垃圾收集行為至關重要,以避免潛在的內存洩...
    程式設計 發佈於2025-04-26

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3