Re: [理工] [資結]-交大97

[qazwsxee (小堯)]

※ 引述《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
推 polomoss:這種考試想得出來嗎~?
→ qazwsxee:應該有別的方法XD，不然此法太花時間思考了
推 FRAXIS:Dynamic Programming....
→ qazwsxee:3樓說的方法，我沒學過~(在演算法嗎)
推 FRAXIS:wiki上面subset sum problem的介紹就寫了..
→ qazwsxee:了解，A(B)=max{Xi + A(B - Xi) | Xi<= B}，A(0)=0 感謝
推 nonagoner:沒學過+1 謝謝解答~