※ 引述《nonagoner (哈)》之銘言： : Given a set of integers X={x1,x2,...,xn} and an integer bound B, design an : algorithm that determines whether a subset X' of X exists such that all : element of X' sum to exactly B. : 本來想寫成從大的整數開始取至小的不大於B的總和看是否存在子集，但是好像會忽略一 : 些排列順序，請問這題要怎麼取出正確子集呢?感謝高手解答 題目想找:是否存在 某個X子集，其整數和正好是B這個數 max(X') :取出集合中的最大值 count(X'): X'的元素個數 function main() { for(int i=1;i <= n;i++) //收集小於等於B的元素 { if(Xi <= B) X' += Xi; } while (count(X')!=0) // 用while迴圈 + 遞迴去解 { if XD(max(X')) return true; else X'-= max(X'); } return false; //若脫離上方的while迴圈，表示沒有此子集! } function XD(int A) //遞迴副程式 { if (A==B) return true; for(int i=1;i <= count(X'),i++) { A = A + Xi; //嘗試 新A值=A值+Xi值 if (A==B) //新A值若等於B，即成立。回傳true給呼叫此副程式的位置 return true; else if(A>B) //若大於，減回去，回到上方for迴圈繼續下一個Xi A = A - Xi; //因為是大於，不用去考慮後續， //因為再怎麼遞迴加還是大於。 else if(A<B) //若小於，以此 新的A值去做 遞迴 { //若後續的遞迴有成功達成 A==B，就回傳true。 X' -= Xi; //暫時減去 if XD(A) //遞迴去做，若XD(A)接受到的是true， return true; //即是後續 成功達成 A==B，就回傳true給呼叫此副程式的位置 else X' += Xi; //失敗就把剛剛移除的Xi放回，回到上方for繼續檢測下一個Xi值 } } } 本來是想用文字敘述~~可是越寫越長~而且用文字敘述有點亂~ 結果就變成 遞迴程式碼了 XD ㄧ開始會取出一個 大的子集 ，其內容元素:單ㄧ個都小於等於B (因為 集合中 大於B的數 沒用途!) 若此大集合的個數為0 => X每個元素都大於B~不可能有其和=B的子集=>false 若此大集合的個數>0 先取最大值 檢測是否=B? 若小於 去ㄧ層遞迴檢測 (A+某Xi)=B? 若(A+某Xi)再小於B 去第二層遞迴檢測 (A+某Xi+某Xj) =B? ... .. 遇到大於 就for迴圈 換ㄧ個Xi重新加回 ，繼續往下遞迴檢測 -- ～剝好了，小心燙喔～ ◢◤ ◢︴◤ ▆ ▆喔喔～ ◢ ˋ◢██◣ ◢██◣◢ 哇～ ◢◤ ◣◢██◣◥█ ρ◤ ██◢◤ █◥◥◥ ◤◤◤ █ ˊ你好體貼喔～ ◢◤ █ ◥◥◥ ∴ ◣ ██◢◤ ◤ ● ●⊿ ●●▄ ◥ ◢◤唉呀！ ◤ ● ＜ζ█◥◣ ◢◤ ◥██ ◤◣ ◥▼"█◤◣ ◢◤好燙～ˋ ◢◥█"▅／▊█◣ ◢◤ ◢◣██◤ ◢▏█▉◣ ◢◤ ◢██╲ █︴◤ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.39.216.58