• 0
كيمو الذيب

مساعدة في rucksack problem

سؤال

السلام عليكم ورحمة الله وبركاته 

 

أنا سعيد بإنضمامي لهذا المنتدى الرائع 

 

بل وفخور كوني أحد أعضاء منتداكم الموقر وهذا أول موضوع لي .

 

قرأت بعض الدروس هنا وتابعت بعضها .. وشاكر لكم كرمكم في إثراء المنتدى 

 

 

--------------------------------- شرح الفكرة ---------------------------

 

أريد مساعدتكم في كتابة برنامج السلام عليكم ورحمة الله وبركاته 

 

أنا سعيد بإنضمامي لهذا المنتدى الرائع 

 

بل وفخور كوني أحد أعضاء منتداكم الموقر وهذا أول موضوع لي .

 

قرأت بعض الدروس هنا وتابعت بعضها .. وشاكر لكم كرمكم في إثراء المنتدى 

 

 

--------------------------------- شرح الفكرة ---------------------------

 

أريد مساعدتكم في كتابة برنامج rucksack problem أو knapsack problem

 

ولمن يريد أن يقرأ عن فكرتها 

 

http://ar.wikipedia.org/wiki/%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%AD%D9%82%D9%8A%D8%A8%D8%A9_%D8%A7%D9%84%D8%B8%D9%87%D8%B1

 

486px-Knapsack.svg.png

 

وفكرتها بإختصار هي : 

 

أن تضع بالشنطه المكعبات الأعلى قيمة بشرط أن لا تتجاوز وزن معين 

 

مثال 

 

كما في الصورة أعلاه :

 

ندخل بالشنطة المكعب الأصفر أولا لأنه الأعلى قيمة 

 

ثم يرفض المكعب الأخضر لأنه لو أضفناه لتجاوزنا الوزن المحدد لنا وهو 15 KG

 

ثم يدخل الرمادي 

 

ثم الأزرق  ثم البرتقالي .. وهكذا 

 

-------------------------------------- محاولاتي -------------------------------------------------

 

 

كونت ثلاث مصفوفات 

 

مصفوفة للوزن [ weight ]  << من المستخدم 

 

مصفوفة للقيمة [ value ] <<  من المستخدم 

 

مصفوفة للنسبة بين الوزن والقيمة [  check ] << يحسبها البرنامج 

 

وسويت function  يعمل كل المقارنات والحسابات 

#include <iostream>using namespace std;float solve(float set,float weight[5],float value[5],float check[5]){for(int i=0;i<5;i++){if(set>0){if(weight[i]<set&&weight[i+1]<set){if(check[i]>check[i+1]){cout<<weight[i]<<"  "<<value[i]<<endl;}elsecout<<weight[i+1]<<"  "<<value[i+1]<<endl;}}}}int main(){float max,set;cout<<"\nEnter the wieght of the bag: ";cin>>max;max=set;float weight[5],value[5];float check[5]; for(int i=0;i<5;i++){cout<<"\nEnter a weight: ";cin>>weight[i];cout<<"\nEnter a value: ";cin>>value[i];}for(int i=0;i<5;i++){check[i]= value[i]/ weight[i];};solve(set,weight[5],value[5],check[5]);char a;cin>>a;    return 0;}

السؤال هو : كيف أحذف القيمة من المصفوفة بعد مقارنتها ؟ حتى لا يعيد مقارنته من جديد 

 

إن كان عندي غلط بالفكره 

 

أو لديكم طريقه أفضل فأنا أرحب بذلك 

 

وكلنا أجتمعنا لنتعلم 

 

شاكر لكم مقدما 

 

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

13 إجابة على هذا السؤال .

  • 0

كيف أحذف القيمة من المصفوفة بعد مقارنتها ؟

لا يمكنك حذف القيمة ولكن أمامك عدة خيارات منها :

1- ضع في المصفوفة قيمة مميزة مثلاً -1 وعدّل الكود بحيث يتجاوز هذه القيمة

2- استعمل linked list بدلاً من المصفوفة

 


إن كان عندي غلط بالفكره 

 

أو لديكم طريقه أفضل فأنا أرحب بذلك 

 

المسألة التي تحلها مشهورة وهي ليست مجالاً للتفكير فالحلول منتشرة على النت .. ولكن أرغب بأن أخبرك أن المسألة هذه اسمها Knapsack 1/0 أي أننا نضع العنصر أو لا نضعه 1 أو 0 وحلّها  باستخدام Dynamic Programming

وهو موجود على النت .. ابحث عنه :)

بالتوفيق

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أشكرك أخي مصطفى على ردك وأهتمامك 

 

قبل أن أنزل الموضوع أنا بحثت بالنت ووجدت بعض الأكواد 

 

وحتى بعد ردك وإعطائي بعض الكلمات للبحث 

 

قرأت أكثر 

 

لكن لم أفهم بعض الأكواد 

 

والمخرج إما 1 أو 0  

 

وأنا أريد أن يخرج لي مجموع قيمة الشنطه بالدولار

 

 

 

 

1- ضع في المصفوفة قيمة مميزة مثلاً -1 وعدّل الكود بحيث يتجاوز هذه القيمة

 

عفوا لم أفهم هذه النقطه 

 

أين أضيفها ؟؟ 

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

والمخرج إما 1 أو 0  

هذا يعني أن العنصر (المكعب مثلاً ) سيتم أخذه أو لا .. لأنه لا يوجد في هذه المسألة أخذ نسبة من الشيء .. مثلاً : لا يمكننا أخذ 0.789 من المكعب إما أن نأخذه أو ألا نأخذه

 


 

اقتباس

 

 

1- ضع في المصفوفة قيمة مميزة مثلاً -1 وعدّل الكود بحيث يتجاوز هذه القيمة

 

عفوا لم أفهم هذه النقطه 

 

أين أضيفها ؟؟

ألم تقل أنك تريد طريقة لحذف عنصر من المصفوفة كي لا تعيد اختباره ؟ :)

بدلاً من الحذف قم بإسناد -1 لهذا العنصر ..

وعندما تريد اختبار العناصر تأكد أن العنصر مغاير لـ -1 يمعنى انه غير محذوف

 

جميع نتائج البحث التالية تحوي حل المسألة

 

بالتوفيق

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

و عليكم السلام و رحمة الله و بركاته اخي اهلا بك معنا في هذا النادي الماتع و ارجو ان تجد كل ما تبحث عنه هنا 

اولا على حسب ما فهمت من الكود الخاص بك و من سؤال التمرين هو ان تقوم باخذ اكبر قيمة في المكعبات و ان تطبعها للمستخدم على ان لا يتجاوز وزن المكعبات اجمالا الحد الاقصى 

و من هنا فانت تحتاج الى مصفوفة رقمية للاوزان و مصفوفة رقمية للاسعار و الحد الاقصى لتحمل الحقيبة ...حسنا هذا جيد 

اذن حسب هذا فانني على ما اعتقد و حسب فهمي لسؤالك فانني ارى انه لا حاجة لهذه المصفوفة 

for(int i=0;i<5;i++){check[i]= value[i]/ weight[i];};

لاننه يمكننا استخدام المصفوفتين السابقتين فقط اي الخاصة بالاوزان و الاسعار

و انا جاءتني فكرة ربما تفيدك او لا تفيدك و هي ان تقوم بترتيب المصفوفة الخاصة بالاسعار من الاكبر الى الاصغر و بالتاكيد ستقوم بتغير مصفوفة الاوزان معها و اي قيمة تقوم بترتيبها اسند اليها قيمة لا يمكن ان تكون وزنا او سعرا اي مثلا -5 أو -1 او لك حرية الاختيار و تستثنيها ضمن شرط تضعه انت و بعد الانتهاء من الترتيب فانك ضمنت ان محتوى اول خانة هو اكبر سعر فتاخذه و تضيف اليه القيم التي تليه فان كان المجموع الناتج للعناصر اقل من الحد الاقصى تطبعه و ان لم يكن اقل فانك تتجاوزه هذه هي فكرتي :)  و أمل ان تكون قد فهمتها قليلا ^_^ و ان لم تفهم فاسالني و ساحاول ان افيدك بقدر ما استطيع  :lol:

بالتوفيق لك   

تم تعديل بواسطه tantie L
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

فكرتك أختي tantie L صحيحة بالفعل وممتازة ولكن ليس لحالة 1/0 أي أنها صحيحة بالفعل عندما يمكننا أخذ نسبة من آخر مكعب ممكن ..

وهي تعطي غالباً حلاً جيداً هنا ولكنه ليس الأمثل (not optimal)

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

عذرا اخي لم افهم قصدك جيدا من 0/1 

فالمطلوب هو طباعة الاوزان المقبولة و الاسعار الخاصة بها و ليس طباعة بانها مقبولة او ﻻ فعلا نستطيع استخدام 0/1 كناتج لدالة تبين امكانية قبول هذا المكعب او لا و لكن المخرجات المطلوبة هي الاوزان و اسعارها (اكيد المقبولة) 

هل يمكنك ان تخبرني عن فكرة الحل الامثل؟

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أنظر البرنامج التالي:

#include <iostream>#include <vector>using namespace std;struct Box{	float price;	float weight;};struct Bag{	Bag(float mw) : max_weight(mw) {}	bool add(const Box&);	float get_total_weight();	float get_total_price();private:	float max_weight;	vector<Box> boxes;};int main(){	float weight;	cout << "Enter the weight of the bag: ";	cin >> weight;	Bag bag(weight);	int count = 0;	cout << "How many boxes to add into bag: ";	cin >> count;		for(int i=0; i<count; ++i)	{		Box box;		cout << "\nEnter a weight: ";		cin >> box.weight;		cout << "Enter a value: ";		cin >> box.price;		if (!bag.add(box))			cout << "Can't add this box to the bag cause it will become overweight.\n";	}	cout << "\nTotal weight in bag: " << bag.get_total_weight();	cout << "\nTotal value in bag: " << bag.get_total_price();}float Bag::get_total_weight(){	float total = 0;	int count = boxes.size();	for(int i=0; i<count; ++i)		total += boxes[i].weight;	return total;}float Bag::get_total_price(){	float total = 0;	int count = boxes.size();	for(int i=0; i<count; ++i)		total += boxes[i].price;	return total;}bool Bag::add(const Box& box){	if ((get_total_weight() + box.weight) > max_weight)		return false;	boxes.push_back(box);	return true;}

و الله ولي التوفيق

تم تعديل بواسطه C++er
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

@ ++C

اهلا بك اخي جربت الكود الخاص بك فقمت بادخال القيم الموجودة في المثال 

قبل وزن 12 و قيمة 4 

و قبل وزن 1 و قيمة 2

لكن لم يقبل وزن 4 و قيمة 10

صحيح هذا عائد الى الوزن الذي و ضعته كحد اقصى الا و هو 15 

لكن المطلوب في نص التمرين هو ان يدخل المكعبات حسب القيمة الاكبر على ان ﻻ يتجاوز الحد الاقصى

فمثلا عندما ادخل القيم التالية 4 - 2 - 10 - 1 - 2 

و الاوزان التالية 12 - 1 - 4 - 1 - 2

فانه سيدخل المكعب الثالث لانه اعلى قيمة اي 10 و وزنه 4 ثم ينتقل الى القيمة الاكبر الثانية و عي 4 لكن الوزن 12 لا يحقق الشرط الثاني فنتجاوزه و هكذا دواليك الى ان ننهي جميع القيم فتكون الحقيبة تحوي الوزن 4 - 1 - 2 - 1 و قيمها على الترتيب هي 10 - 2 - 2 - 1 فيكون ثمن الحقيبة هو 15 $ هذا هو المطلوب 

لكن صراحة اهنئك على هذا الكود فهو رائع  :)

لك احترامي

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم ..

 

هذه تجربتي ..

لا أعلم إن كانت صحيحة 100%100 ولكن طبقتها على المعطيات الموجودة وأعطت الناتج المطلوب

#include <stdio.h>void Order(int arr[],int Length,int arr3[]){    int Great=0,x,y; // Variable Uses In Loops Or To Save Greater Number    int z=-1,z1; // Variable For Save Current ID Of Array    int arr2[Length-1],arr4[Length-1]; // Arrays To Save New Data    while(z++<Length-1)    {        for(x=0;x<Length;x++)        {if(arr[x]>Great){Great=arr[x];y=x;z1=arr3[x];}} // Find Greater Number        arr2[z]=Great;arr4[z]=z1; // New Data From Great To Small        Great=0;        arr[y]=-1; // Delete Greater Number    }    z=-1;    while(z++<Length-1){arr[z]=arr2[z];arr3[z]=arr4[z];} // Send New Data To Old Storge}int main(){    int CubeW,Bag; // CubeW is numbers of weights --- Bag is weight of bag    int x=0,PriceOfBag=0,WeightBag=0; // x is for loops --- PriceOfBag is Price of bag --- WeightBag is weight which will take to bag    printf("Enter Num of Weights:\n"); // Get Number of weights    scanf("%d",&CubeW);    int arr[CubeW],arr3[CubeW]; // The arrays will be used    printf("Enter Weights:\n"); // Get The Weights    while(x++<CubeW){scanf("%d%d",&arr[x],&arr3[x]);}    printf("Enter Weight of Bag:\n"); // Get Weight of bag    scanf("%d",&Bag);    Order(arr,CubeW,arr3); // Order the arrays    for(x=0;x<CubeW-1;x++)    {if(arr3[x]<Bag && WeightBag+arr3[x]<=Bag){PriceOfBag+=arr3[x];}}    printf("%d",PriceOfBag); // Show the price of bag    return 0;}

التجربة ..

 

post-219398-0-96400200-1387918250_thumb.

 

تحياتي  ^_^

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

@ bahbah

و عليكم السلام و رحمة الله و بركاته

تجربة جيدة و اختصرت الطريق علينا  ;)

طبقت الكود الخاص بك و بنفس المدخلات التي ادخلتها انت و بنفس الترتيب و انتظرت ان تكون النتيجة 15 لكن كانت -16 و في ترتيبات اخرى ايضا كانت النتيجة سالبة؟

و هل يمكنك ان تجعل شكل الكود اكثر وضوحا في مرات قادمة فقط لتسهيل فهمه و تتبعه

و لك بالغ الشكر على هذه التجربة  :)  

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

عذراً ، كنت مستعجلاً أمس ، لأني حللتها في وقت متأخر ...

لذلك لم أتعب نفسي في تجربته ..

 

 

الكود بعد التصحيح ..

#include <stdio.h>void Order(int arr[],int Length,int arr3[]){    int Great=0,x,y; // Variable Uses In Loops Or To Save Greater Number    int z=-1,z1; // Variable For Save Current ID Of Array    int arr2[Length-1],arr4[Length-1]; // Arrays To Save New Data    while(z++<Length-1)    {        for(x=0;x<Length;x++) // Find Greater Number        {            if(arr[x]>Great)            {                Great=arr[x];                y=x;z1=arr3[x];            }        }        arr2[z]=Great; // New Data From Great To Small        arr4[z]=z1;        Great=0;        arr[y]=-1; // Delete Greater Number    }    z=-1;    while(z++<Length-1) // Send New Data To Old Storge    {        arr[z]=arr2[z];        arr3[z]=arr4[z];    } }int main(){    int CubeW,Bag; // CubeW is numbers of weights --- Bag is weight of bag    int x=-1,PriceOfBag=0,WeightBag=0; // x is for loops --- PriceOfBag is Price of bag --- WeightBag is weight which will take to bag    printf("Enter Num of Weights:\n"); // Get Number of weights    scanf("%d",&CubeW);CubeW--;    int arr[CubeW],arr3[CubeW]; // The arrays will be used    printf("Enter Weights:\n"); // Get The Weights    while(x++<CubeW) // While Loop For Get Weights With Price    {        scanf("%d %d",&arr[x],&arr3[x]);    }    printf("Enter Weight of Bag:\n"); // Get Weight of bag    scanf("%d",&Bag);    Order(arr,CubeW+1,arr3); // Order the arrays    for(x=0;x<CubeW+1;x++)    {        if(arr3[x]<=Bag && WeightBag+arr3[x]<=Bag)        {            PriceOfBag+=arr[x];            WeightBag+=arr3[x];        }    }    printf("%d",PriceOfBag); // Show the price of bag    return 0;}

الكود بدون التعليقات (إذا كنتم منزعجين منها) :

#include <stdio.h>void Order(int arr[],int Length,int arr3[]){    int Great=0,x,y;    int z=-1,z1;    int arr2[Length-1],arr4[Length-1];    while(z++<Length-1)    {        for(x=0;x<Length;x++)        {            if(arr[x]>Great)            {                Great=arr[x];                y=x;z1=arr3[x];            }        }        arr2[z]=Great;        arr4[z]=z1;        Great=0;        arr[y]=-1;    }    z=-1;    while(z++<Length-1)    {        arr[z]=arr2[z];        arr3[z]=arr4[z];    } }int main(){    int CubeW,Bag;    int x=-1,PriceOfBag=0,WeightBag=0;    printf("Enter Num of Weights:\n");    scanf("%d",&CubeW);CubeW--;    int arr[CubeW],arr3[CubeW];    printf("Enter Weights:\n");    while(x++<CubeW)    {        scanf("%d %d",&arr[x],&arr3[x]);    }    printf("Enter Weight of Bag:\n");    scanf("%d",&Bag);    Order(arr,CubeW+1,arr3);    for(x=0;x<CubeW+1;x++)    {        if(arr3[x]<=Bag && WeightBag+arr3[x]<=Bag)        {            PriceOfBag+=arr[x];            WeightBag+=arr3[x];        }    }    printf("%d",PriceOfBag);    return 0;}

تحياتي  ^_^ 

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

يا جماعة المسألة ليست في أن نملاً الحقيبة كيفما كان بل بأعلى سعر ممكن ..

فكرة الترتيب سبق وذكرت أنها جيدة ولكنها لا تعطي الحال المثال دوماً ..ولكن ليس   أي ترتيب بل حصراً : ترتيب مصفوفة تحوي النسبة( السعر على الوزن ) وبذلك تكون أعلى قيمة فيها هي السعر الأعلى والوزن الأقل

قصة السؤال لها عدة روايات منها : سارق دخل الى بيت ماذا سيأخذ ؟ كل ما خفّ وزنه وارتفع ثمنه .. لا يكفي أن يكون ثمنه مرتفعاً فقط .. ولا أن يكون خفيفاً فقط ..

ولتأكيد أن فكرة الترتيب غير مثالية في حالة 1/0 أي إما أن نأخذ العنصر أو لا .

انظروا مثلاً إلى المثال التالي

لنفرض أن الحقيبة تتحمل الوزن 10

وفيما يلي سأذكر الثمن ثم الوزن ثم نسبة الثمن إلى الوزن

4 -  4      ----- 1

9 - 10     ----- 0.9

8 - 8       ----- 1

عندما نرتب القيم حسب نسبة الثمن إلى الوزن سيكون الترتيب كما يلي

4 -  4      ----- 1

8 - 8       ----- 1

9 - 10     ----- 0.9

 

ويمكنكم تجريب أكوادكم وسيتبين أنها ستعطي 4 أو 8 وليس 9 وهو الحل الأمثل

 

أنصح الجميع بأن يكتب كود يوجد جميع الاحتمالات (Brute Force) لمعرفة صحة الكود من خطئه وأن يجرب الكود على عدة حالات مختلفة

 

بالتوفيق

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

يا جماعة المسألة ليست في أن نملاً الحقيبة كيفما كان بل بأعلى سعر ممكن ..

فكرة الترتيب سبق وذكرت أنها جيدة ولكنها لا تعطي الحال المثال دوماً ..ولكن ليس   أي ترتيب بل حصراً : ترتيب مصفوفة تحوي النسبة( السعر على الوزن ) وبذلك تكون أعلى قيمة فيها هي السعر الأعلى والوزن الأقل

قصة السؤال لها عدة روايات منها : سارق دخل الى بيت ماذا سيأخذ ؟ كل ما خفّ وزنه وارتفع ثمنه .. لا يكفي أن يكون ثمنه مرتفعاً فقط .. ولا أن يكون خفيفاً فقط ..

ولتأكيد أن فكرة الترتيب غير مثالية في حالة 1/0 أي إما أن نأخذ العنصر أو لا .

انظروا مثلاً إلى المثال التالي

لنفرض أن الحقيبة تتحمل الوزن 10

وفيما يلي سأذكر الثمن ثم الوزن ثم نسبة الثمن إلى الوزن

4 -  4      ----- 1

9 - 10     ----- 0.9

8 - 8       ----- 1

عندما نرتب القيم حسب نسبة الثمن إلى الوزن سيكون الترتيب كما يلي

4 -  4      ----- 1

8 - 8       ----- 1

9 - 10     ----- 0.9

 

ويمكنكم تجريب أكوادكم وسيتبين أنها ستعطي 4 أو 8 وليس 9 وهو الحل الأمثل

 

أنصح الجميع بأن يكتب كود يوجد جميع الاحتمالات (Brute Force) لمعرفة صحة الكود من خطئه وأن يجرب الكود على عدة حالات مختلفة

 

بالتوفيق

 

اها .. ما أعتقدت أننا يجب أن نفكر مثل السارق ..

أنا نظرت فقط إلى الموضوع وإستنتجت المطلوب ..

 

شكراً على التوضيح ..  ;)

 

هذا الكود بعد التعديل :

#include <stdio.h>void Order(int arr[],int Length,int arr3[]){    int x,y;double Great=0,GreatX=0,b;    int z=-1,z1;    int arr2[Length-1],arr4[Length-1];    while(z++<Length-1)    {        for(x=0;x<Length;x++)        {b=(double)arr[x]/(double)arr3[x];if(b>Great){GreatX=arr[x];Great=b;y=x;z1=arr3[x];}}        arr2[z]=GreatX;arr4[z]=z1;        Great=0;        arr[y]=-1;    }    z=-1;    while(z++<Length-1){arr[z]=arr2[z];arr3[z]=arr4[z];}}int main(){    int CubeW,Bag;    int x=-1,PriceOfBag=0,WeightBag=0;    printf("Enter Num of Weights:\n");    scanf("%d",&CubeW);CubeW--;    int arr[CubeW],arr3[CubeW];    printf("Enter Weights:\n");    while(x++<CubeW)    {        scanf("%d %d",&arr[x],&arr3[x]);    }    printf("Enter Weight of Bag:\n");    scanf("%d",&Bag);    Order(arr,CubeW+1,arr3);    for(x=0;x<CubeW+1;x++)    {        if(arr3[x]<=Bag && WeightBag+arr3[x]<=Bag)        {            PriceOfBag+=arr[x];            WeightBag+=arr3[x];        }    }    printf("Price of bag:%d\tWeight of bag:%d\n",PriceOfBag,WeightBag);    return 0;}

وهذه ثلاث تجارب ..

 

التجربة الخاصة بالموضوع ، تجربة الأخ مصطفى ، تجربة آخرى من عندي ..

 

post-219398-0-20021000-1387976368_thumb.

 

post-219398-0-56497000-1387976501_thumb.

 

post-219398-0-25759900-1387976533_thumb.

 

تحياتي  ^_^

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .