algorithm - 如何使用贪心算法跟踪背包 pr0blem？

Question

问题是如何使用以下信息用贪心算法跟踪背包问题？

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

如果有人能帮助我理解这一点或指出我正确的方向，我将不胜感激。

Answer 1

好吧，如果它是“分数背包”（即你可以拿走部分物品），那么这很容易：

这些项目是（作为价格，重量对）[(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]

如果你不能取小数项，那么这种贪婪的方法可能不会给你最佳解决方案。

Answer 2

第一步，即 1. 取 (13, 3): cap = 12, price = 15，因为加了 3 件，所以价格会是 13*3=39... 同理. 当再添加 2 个时，则添加 7*2=14。所以第 2 步的成本将是 39+14=53。

Answer 3

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

}