زمان کنونی: ۲۱ اردیبهشت ۱۴۰۰, ۰۳:۲۱ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تست از NP

ارسال:
  

vijay پرسیده:

تست از NP

[تصویر:  62084_1_1379096282.png]

جواب سوال ۳ گفته شده .دلیلش چیه؟؟؟؟؟

۰
ارسال:
  

Masoud05 پاسخ داده:

RE: NPتست

اینکه گفته x 0 یا ۱ هست یعنی کوله پشتی ۰-۱ نه کوله پشتی کسری .
کوله پشتی ۰-۱ به ۲ روش اصلی پویا و بازگشت به عقب حل میشه . مرتبه اجرایی به روش
۱- پویا‌: [tex]o(nw)[/tex] هست
۲- بازگشت به عقب [tex]o(2^n)[/tex] هست
جواب مینیمم دو مقدار بالا هست . در شرایطی که w نسبت به n خیلی بزرگ باشه( نمایی )مقدار nw نمایی میشه پس جواب کل مینیمم ۲ مقدار نمایی هست که میشه یه مقدار نمایی( نه چند جمله ای )

۰
ارسال:
  

Bache Mosbat پاسخ داده:

NPتست

این مسئله‌ی کوله پشتی ۰ , ۱ هست که با استفاده از داینامیک پروگرمینگ راه حل چند جمله ای بر حسب پارامتر ورودی (pseudo polynomial) برای اون وجود داره.
برای دیدن راه حلش هم می تونین به کتاب های الگوریتم مراجعه کنین که به تفصیل توضیح دادن!



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  PDA and NPDA gmh1993 ۱ ۹۶۹ ۱۱ خرداد ۱۳۹۳ ۰۷:۵۵ ب.ظ
آخرین ارسال: aamitis
  کلاس رفع اشکال و حل تست کلاس رفع اشکال و حل تست pedram25teh ۲ ۱,۵۸۱ ۲۹ دى ۱۳۹۱ ۱۲:۵۳ ق.ظ
آخرین ارسال: Fardad-A
Photo سوال از Npda mi1s0n ۱۱ ۲,۶۹۰ ۲۴ مرداد ۱۳۹۱ ۰۴:۱۵ ب.ظ
آخرین ارسال: Jooybari
  اول ریفرنس بعد کتاب درس و تست؟ یا اول کتاب درس و تست (مثل مقسمی) و بعد ریفرنس؟ Amir V ۲ ۲,۶۰۴ ۲۱ فروردین ۱۳۹۱ ۰۱:۱۳ ق.ظ
آخرین ارسال: homa
  الگوریتم یافتن گرامر یک npda پرهام ۱ ۳,۰۷۷ ۱۷ مرداد ۱۳۹۰ ۰۱:۱۳ ق.ظ
آخرین ارسال: ف.ش
  npda در این گرامر masoudkhan ۳ ۱,۴۶۶ ۱۸ خرداد ۱۳۹۰ ۰۳:۲۵ ب.ظ
آخرین ارسال: ف.ش
  [تست] تست ۳۷ آیتی ۸۷ amir2930 ۵ ۳,۳۴۶ ۲۰ بهمن ۱۳۸۹ ۰۹:۳۹ ق.ظ
آخرین ارسال: ف.ش
  راه تستی برای شناسایی زبان dpda از npda چیست ؟ bahar ۱ ۲,۷۴۸ ۰۴ آذر ۱۳۸۹ ۰۸:۰۶ ب.ظ
آخرین ارسال: sepid

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close