مسئله 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)

کوله پشتی

کوله پشتی

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

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

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

کوله پشتی