问题是如何使用以下信息用贪心算法跟踪背包问题?
P=[10,7,12,13,6,20]
W=[3,2,4,3,13,8]
M=15
n=6
如果有人能帮助我理解这一点或指出我正确的方向,我将不胜感激。
问题是如何使用以下信息用贪心算法跟踪背包问题?
P=[10,7,12,13,6,20]
W=[3,2,4,3,13,8]
M=15
n=6
如果有人能帮助我理解这一点或指出我正确的方向,我将不胜感激。
好吧,如果它是“分数背包”(即你可以拿走部分物品),那么这很容易:
这些项目是(作为价格,重量对)[(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]
如果你不能取小数项,那么这种贪婪的方法可能不会给你最佳解决方案。
第一步,即 1. 取 (13, 3): cap = 12, price = 15,因为加了 3 件,所以价格会是 13*3=39... 同理. 当再添加 2 个时,则添加 7*2=14。所以第 2 步的成本将是 39+14=53。
#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;
}