پاورپوینت مسأله مجموع زیرمجموعه ها

پاورپوینت مسأله مجموع زیرمجموعه ها دارای 10اسلاید با ظاهری زیبا ، متفاوت ، مفید، مختصر و قابل ویرایش می باشد قسمتی از متن را ببینید و در صورت تمایل خرید کنید

پاورپوینت مسأله مجموع زیرمجموعه ها

پاورپوینت  مسأله مجموع زیرمجموعه ها دارای 10اسلاید  با ظاهری زیبا ، متفاوت ، مفید، مختصر و قابل ویرایش می باشد قسمتی از متن را ببینید و در صورت تمایل خرید کنید.

n عدد صحیح مثبت wi و یک عدد صحیح مثبت M وجود دارد. هدف یافتن تمام زیرمجموعه های اعداد صحیح است به طوری که مجموع آنها M باشد. 

مثال:

n=5, M=21, w=(11,5,6,16,10)

5+6+10=21,       5+16=21,            10+11=21

حل با استفاده از روش ایجاد درخت فضای حالت

حل مسأله

برای تعیین گره های وعده گاه اعداد را به صورت غیرنزولی مرتب می کنیم.

در سطح i ام , wi+1 کمترین وزن باقی مانده را دارد.

اگر weight مجموع اعداد تا گره سطح i باشد:

weight+ wi+1 >M  ام غیر وعده گاه i گره

اگر total مجموع اعداد باقی مانده باشد:

weight+ total >M  ام غیر وعده گاه i گره

اگر weight=M آنگاه یک جواب در آن گره به دست آمده و باید به عقب برگشت و مسیر جدید را شروع کرد.

آرایه include[1..n] : در صورتی که عدد iام انتخاب شود include[i]=“yes” در غیر اینصورت include[i]=“no”

الگوریتم مجموع زیرمجموعه ها

void sos(int i, int weight, int total)

{  if (promising(i))

       if (weight = = M)

           cout<

       else

         { include[i+1]=“yes”;

            sos(i+1,weight+w[i+1],total-w[i+1]);     

            include[i+1]=“no”;

            sos(i+1,weight,total-w[i+1]);     

          } 

}                                                       total= w[j],  sos(0,0,total)  فراخوانی اولیه

int promising (int i)

{

  return(weight+total>=M) && (weight= =M || weight+w[i+1]<=M);

روش حل

گره شروع در سطح صفر درخت

در سطح یک همه گره ها به جز گره شروع

در سطح n-1 همه گره ها به جز سطوح قبل

نکات:

i امین گره همجوار گره i-1 ام باشد

n-1 امین گره مجاور گره صفر (شروع) باشد.

i امین گره نباید برابر با i-1 گره قبل باشد.

آرایه vindex[0..n-1] از شاخص های گره ها مسیر را نگهداری می کند

تعداد گره های درخت فضای حالت:

1 + (n-1) + (n-1)2+… +(n-1)n-1=

ppt: نوع فایل

سایز: 17.1 KB

تعداد اسلاید:10

برچسب ها : پاورپوینت مسأله مجموع زیرمجموعه ها , دانلود پاورپوینت مسأله مجموع زیرمجموعه ها , پاورپوینت مسأله مجموع زیرمجموعه ها , مسأله مجموع زیرمجموعه ها , دانلود پاورپوینت , پاورپوینت , تحقیق , جزوه , مقاله , پایان نامه , پروژه , دانلود تحقیق , دانلود جزوه , دانلود مقاله , دانلود پایان نامه , دانلود پروژه