Как отследить рюкзаки, используя жадный алгоритм? - PullRequest
Новая
       40

Как отследить рюкзаки, используя жадный алгоритм?

1 голос
/ 18 декабря 2011

Вопрос в том, как отследить проблему ранца с помощью жадного алгоритма, используя следующую информацию? 

P=[10,7,12,13,6,20]
W=[3,2,4,3,13,8]
M=15
n=6

Буду признателен, если кто-нибудь поможет мне понять это или покажет мне правильное направление.

Ответы [ 3 ]

2 голосов
/ 18 декабря 2011

Ну, если это «дробный рюкзак» (то есть вы можете взять дроби предметов), то это легко:

Предметы (как цена, вес пары) [(10, 3), (7, 2), (12, 4), (13, 3), (6, 13), (20, 8)]

Интуитивно вы захотите сначала получить предмет, который обеспечит большую ценус меньшим весом.Итак, давайте отсортируем элементы по их соотношению цены и веса:

[(13, 3), (7, 2), (10, 3), (12, 4), (20, 8),(6, 13)]

Теперь, пока у вас не закончится емкость или предмет, возьмите как можно больше самого ценного предмета. 

0. cap = 15, price = 0
1. Take (13, 3): cap = 12, price = 13
2. Take (7, 2): cap = 10, price = 20
3. Take (10, 3): cap = 7, price = 30
4. Take (12, 4): cap = 3, price = 42
5. Take (20, 8): cap = 0, price = 49.5
   [in this step, you have capacity to take 3 units, so take 3 units of the 5th item, the price of which is 3*20/8]

Если вы не можете взять дробные предметытогда такой жадный подход может не дать вам оптимального решения.

0 голосов
/ 25 ноября 2013 
#include<iostream>
#include<time.h>
using namespace std;
int r;
int* sort(int list[],int n)
    {

        int temp;
        bool swap =true;
        int i;
        while(swap)
        {
        for(i=0;i<n-1;i++)
            {
            for(int j=i+1;j<n;j++)

                {
                if(list[i]>list[j])
                    {
                    temp=list[j];
                    list[j]=list[i];
                    list[i]=temp;
                    swap= true;
                    }else
                        {
                        swap= false;
                        }

                }
            }
        }
        return (list);

    }
int* knapsack(int list[],int k)
{
    const int n=6;
    int c=0;

    int ks[n];
    int sum=0;
    int u;
    for(int i=0;i<n;i++)
    {   
    sum=sum+list[i];
        if(sum<=k)
        {
            u=list[i];
            ks[i]=u;
            list[i]=i+1;
            c++;
            //cout<<"Index number in sorted list : "<<i+1<<" "<<endl;
        }
    }

    r=c;
    return (list);

}

int main() 
{
    double difference1,difference2;
    clock_t start,end;   
    const int m=5;
    int list[m]={8,6,7,4,9};
    cout<<"Your list of sizes of parcel : ";
    for(int i=0;i<m;i++)
    {
        cout<<list[i]<<" ";
    }
    cout<<endl<<endl;

    start = clock();

    int* x=sort(list,m);  //call to sorting function to sort the list in increasing size order.

    end = clock();
    difference1=((start-end)/CLOCKS_PER_SEC);

    cout<<"Sorted list of sizes of parcel : ";
    for (int j = 0; j <m; j++) 
    {cout<<x[j]<<" ";}

    cout<<endl<<endl;
    111
    int k=24;   //Size of sack

    start = clock();

    int* g= knapsack(list,k); //call to knapsack function

    end = clock();
    difference2=((start-end)/CLOCKS_PER_SEC);

        cout<<"Indexes taken from sorted list : ";
                for(int l=0;l<r;l++)
                {
                cout<<g[l]<<" ";
                }
        cout<<endl<<endl;
        cout<<"Time elapsed : "<<(difference1+difference2)<<endl<<endl;

}
0 голосов
/ 04 февраля 2013

На первом шаге, то есть 1. Взять (13, 3): cap = 12, цена = 15, поскольку добавлено 3 элемента, поэтому цена будет 13 * 3 = 39 ...таким же образом.При добавлении еще 2 добавляется 7 * 2 = 14.Таким образом, стоимость на шаге 2 будет 39 + 14 = 53.

...