贪心算法解决背包问题

背包问题：

与0-1背包问题类似，所不同的是在选择物品i装入背包中时，可以选择物品i的一部分，而不一定要全部装入背包中，1<=i<=n。

此问题的形式化描述是，给定C>0,Wi>0,Vi>0,1<=i<=n,要求找出一个n元向量（x1,x2,....xn），0<=xi<=1,1<=i<=n,使得sum(Wixi)<=C,而sum(ViXi)达到最大。

问题分析：

虽然背包问题与0-1背包问题极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

求解基本步骤：

首先计算每种物品单位重量的价值vi/wi，然后依据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品尽可能多的装入背包。依次策略一直地执行下去，直到背包装满为止。具体算法描述如下：

public static float knapsack(float c,float[]w,float[]v,float[]x)
{
int n=v.length;                            
Element[]d=new Element[n];
for(int i=0;i<n;i++)
d[i]=new Element(w[i],v[i],i);
MergeSort.mergeSort(d);    //单位价值量大小排序
int i;
float opt=0;
for(i=0;i<n;i++)x[i]=0;  //x[i]记录i物品取的数量，x[i]=1,表示全部取到
for(i=0;i<n;i++)
{
if(d[i].w>c)break;
x[d[i].i]=1;     //注意d[i]与x[i]的映射关系
opt+=d[i].v;
c-=d[i].w;
}
if(i<n)                //表示没有装满
{
x[d[i].i]=c/d[i].w;  //取的d[i].i种物品装满装满剩余部分，一个比例
opt+=x[d[i].i]*d[i].v;
}
return opt;


}

总结：

注意背包问题与0-1背包问题的区别即可。

最后

以上就是大气心锁为你收集整理的贪心算法解决背包问题的全部内容，希望文章能够帮你解决贪心算法解决背包问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。