背包问题的贪心算法.pptx

背包问题的贪心算法4.2背包问题4.2背包问题例4.3贪心算法不能求得0-1背包问题得最优解。
考虑背包问题:n＝3,c＝50kg,(v1,v2,v3)=(60,100,120),
(w1,w2,w3)=(10,20,30).vi/wi=(6,5,4).贪心算法解是(1,1,0),∑vixi=60+100,∑wixi=30;最优解是(0,1,1),∑vixi=100+120,∑wixi=50,4.2背包问题例4.4考虑下列情况下的背包问题:n＝3,c＝20,
(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的四个可行解是（1）取目标函数作为量度标准，即每次选择利润最大的物品装包，使背包获得最大可能的效益值增量。在此量度标准下贪心方法就是按效益值的非增次序，将物品一一装包，直到某一i物品放不下时，取一种能获得最大增量的物品，将它（或其一部分）放入背包，而使最后一次装包也符合量度标准的要求，如：还剩下两个单位的空间，而背包外还有两种物品。，且物品2的24/15=v2/w2较物品3的15/10＝v3/w3效益值高。按此选择策略,得②即(1,2/15,0),∑vixi=28.2.此解是一个次优解。显然，按物品效益值的非增次序装包不能得最优解。原因：容量慢慢消耗，但效益值未能迅速增大。用贪心算法解背包问题的基本步骤：
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
用算法KNAPSACK可实现求背包问题的最优解.
具体算法可描述如下页：
voidKNAPSACK(intn,floatc,floatv[],floatw[],floatx[])
//v[],W[]分别含有按V[i]/W[i]≥V[i+1]/w[i+1]排序的n件物品的//
//效益值和重量；c是背包的容量，x[]是解向量//
{
inti;
for(i=1;i<=n;i++)x[i]=0;//将解向量初始化为0//
floatcu=c;//cu是背包剩余容量//
for(i=1;i<=n;i++)
{
if(w[i]>cu)break;
x[i]=1;
cu=cu-w[i];
}
if(i<=n)x[i]=cu/w[i];
} 对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。
实际上，动态规划算法的确可以有效地解0-1背包问题。定理4.2若V1/W1≥V2/W2≥…≥Vn/Wn，则算法KNAPSACK产生背包问题的一个最优解。
证明基本思想：通过将贪心法的解与任何最优解进行比较来证明。如果这两个解不同，就找出不相等的且下标最小的第一个，从中可推出与假设矛盾的结论。若k<j，则xk=1，因yk≠xk，从而yk<xk。
若k＝j，由于,∑wixi且对于1≤i<j，有xi=yi=1，而对j<i≤n，若xi=0，若xk<yk，显然有∑wiyi>c，与y是可行解矛盾。若yk=xk，与假设yk≠xk矛盾，故yk<xk。如果,∑vizi>∑viyi.，则Y不可能是最优解。如果这两个和数相等。同时Z＝X，则X就是最优解；若Z＝X，则需要重复上面的讨论。或者证明Y不是最优解或者把Y转换成X，从而证明了X也是最优解。证毕。4.3贪心算法的基本要素4.3贪心算法的基本要素4.3贪心算法的基本要素