مساعدة في rucksack problem

اقتباس

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

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

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

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

اقتباس

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

 

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

 

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

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

بالتوفيق

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

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

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

قرأت أكثر 

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

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

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

اقتباس

 

 

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

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

أين أضيفها ؟؟ 

اقتباس

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

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

اقتباس

 

اقتباس

اقتباس

 

 

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

 

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

 

أين أضيفها ؟؟

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

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

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

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

بالتوفيق

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

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

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

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

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

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

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

بالتوفيق لك   

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

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

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

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

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

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

#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.weight;	return total;}float Bag::get_total_price(){	float total = 0;	int count = boxes.size();	for(int i=0; i<count; ++i)		total += boxes.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

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

قبل وزن 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 $ هذا هو المطلوب 

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

لك احترامي

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

هذه تجربتي ..

لا أعلم إن كانت صحيحة 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;
}

التجربة ..

تحياتي  ^_^

@ bahbah

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

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

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

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

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

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

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

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

#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;
}

تحياتي  ^_^ 

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

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

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

ولتأكيد أن فكرة الترتيب غير مثالية في حالة 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) لمعرفة صحة الكود من خطئه وأن يجرب الكود على عدة حالات مختلفة

بالتوفيق

مصطفى 36a2 كتب:

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

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

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

ولتأكيد أن فكرة الترتيب غير مثالية في حالة 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;
}

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

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

تحياتي  ^_^