مسئله 14 (کوله پشتی)

 

 

الگوریتم:

برای حل این مسئله ابتدا ورودی هامون رو دریافت می کنیم و به آنها اندیس اختصاص می دیم و هر کدوم رو توی یک آرایه قرار می دیم. بعد آرایه هامون رو بر اساس ارزش اجناس به صورت نزولی مرتب می کنیم. به طوری که کالا هایی که ارزش بالایی دارن در بالا و کالاهایی که ارزش کمتری دارن در پایین قرار داده می شن. بعد شروع می کنیم به انتخاب کالاها. هرکدوم از کالاهایی که انتخاب می کنیم از ظرفیت کوله پشتی به اندازه وزن کالایی که انتخاب کردیم کم میکنه. بعد از اینکه کالا هامون رو انتخاب و انتخاب شدن(1) یا عدم انتخاب(0) ها رو نیز توی یک آرایه دیگه ریختیم و حداکثر ارزش اجناس رو محاسبه کردیم ، بعد ار اون دوباره آرایه هامون رو بر اساس اندیس مرتب سازی می کنیم تا دوباره به همان ترتیبی که در ورودی دریافت کرده بودیم بیفتد. 

در آخر هم 0 و 1 ها و حداکثر ارزش کالا ها رو نشون می دیم.

برنامه: به زبان c++

 

#include using namespace std; int main() { /////تعریف متغیر ها int n,w,i,j,h,mv=0; /////دریافت تعداد کالا ها و ظرفیت کوله پشتی cin>>n>>w; /////تعریف آرایه ها int *a=new int[n]; int *b=new int[n]; int *c=new int[n]; int *end=new int[n]; /////دریافت ورودی ها و اختصاص اندیس یه آنها for(i=0;i<=n-1;i++){cin>>a[i]>>b[i];c[i]=i;} /////مرتب سازی بر اساس ارزش کالا ها for(j=n-2;j>=0;j--) { for(i=0;i<=j;i++) { if(b[i]=0;j--) { for(i=0;i<=j;i++) { if(c[i]>c[i+1]) { h=a[i];a[i]=a[i+1];a[i+1]=h; h=b[i];b[i]=b[i+1];b[i+1]=h; h=c[i];c[i]=c[i+1];c[i+1]=h; h=end[i];end[i]=end[i+1];end[i+1]=h; } } } /////نمایش وجود یا عدم وجود کالا ها با ترتیب ورودی ها for(i=0;i


مطالب مشابه :


مسئله 14 (کوله پشتی)

مسئله های برنامه نویسی - مسئله 14 (کوله پشتی) - حل مسائل مختلف دنیای برنامه نویسی




سفرنامه ویتنام (سایگون 1)

کوله پشتی نارنجی - سفرنامه ویتنام (سایگون 1) - هوای سفر دارم، کفشهایم را می پوشم و کوله پشتی ام




کوله پشتی

دیشب و پریشب، گفتگوی سردار رادان و فرزاد حسنی از برنامه "کوله پشتی" پخش شد. از نکات جالب بحث




کوله پشتی

طبیعت - کوه - گردشگری - کوله پشتی - طبیعتگردی کلمه ای زیبا تر از “همنورد” برای خطاب تو نیست.




راهنمای خرید کوله پشتی

کوله برنامه 1 روزه با 3 روزه فرق می‌کند، حجم وسایل در زمستان از تنظیم کوله پشتی روی بدن




مثلث طلایی آسیای میانه (سفرنامه ترکمنستان، ازبکستان و تاجیکستان)

کوله پشتی نارنجی - مثلث طلایی آسیای میانه (سفرنامه ترکمنستان، ازبکستان و تاجیکستان) - هوای




کوله پشتی و فرزاد حسنی !!

علاوه بر اینها خود برنامه کوله پشتی باعث گردید که در بخش های مختلفی از روند کاری صدا و سیما




کوله پشتی

کوله پشتی . در ميان وسايل کوهنوردي پس از کفش مهمترين وسيله کوله کوله مناسب بدن و برنامه




برچسب :