归本程子末军 1.50-1背包问题和背包问题 SHANDONG UNIVERSITY OF TECINOLOGY ●0-1背包问题的定义： ●背包问题定义： max max >VX i=1 i= 立wx≤C w,xsC i=1 x∈{0,11≤i≤n) 0≤x,≤1(1≤i≤n) 这2类问题都具有最优子结构性质，极为相似，但背包问 题可以用贪心算法求解，而0-1背包问题却不能用贪心算 法求解。 2025年4月3日
2025年4月3日 11 1.5 0-1背包问题和背包问题 ⚫ 0-1背包问题的定义： ⚫ 背包问题定义： = n i i i v x 1 max 这2类问题都具有最优子结构性质，极为相似，但背包问 题可以用贪心算法求解，而0-1背包问题却不能用贪心算 法求解。 = n i i i v x 1 max ( ) = x i n w x C i n i i i 0,1 1 1 = 0 1 (1 ) 1 x i n w x C i n i i i
白东程子太军 1.50-1背包问题和背包问题 SHANDONG UNIVERSITY OF TECINOLOGY 会是3会公☆ 20 30 50 30 20 20 30 20 20 10 10 10 10 $100 $120 背包容量 =$240 $60 =$220 =$160 =$180 (a)物品规格和背包容量 (b)0-1背包问题的选择策略 (c)背包问题 的贪心选择 2025年4月3日
2025年4月3日 12 10 20 30 50 (a)物品规格和背包容量 $60 $100 $120 背包容量 20 30 ＝$220 10 20 ＝$160 10 30 ＝$180 (b)0-1背包问题的选择策略 10 20 20 ＝$240 (c)背包问题 的贪心选择 1.5 0-1背包问题和背包问题
归本程子末军 SHANDONG UNIVERSITY OF TECHNOLOGY 用贪心算法解背包问题的基本步骤： 首先计算每种物品单位重量的价值V/Wⅵ，然后，依贪心 选择策略，将尽可能多的单位重量价值最高的物品装入背包。 若将这种物品全部装入背包后，背包内的物品总重量未超过 C,则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页： 2025年4月3日 13
2025年4月3日 13 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心 选择策略，将尽可能多的单位重量价值最高的物品装入背包。 若将这种物品全部装入背包后，背包内的物品总重量未超过 C，则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页： 用贪心算法解背包问题的基本步骤：
山东程子太军 1.50-1背包问题和背包问题 SHANDONG UNIVERSITY OF TECINOLOGY 器会会合会的六3会的品条 void Knapsack(int n,float M,float vI,float wi,float x[) { 算法knapsack Sort(n,v,w); 的主要计算时间在 int i; 于将各种物品依其 for(=1;i<=n;i++)x0=0; 单位重量的价值从 大到小排序。因此， float c=M; 算法的计算时间上 for (i=1;i<=n;i++){ 界为 if (wli]>c)break; o(nlogn)。 为了证明算法的正 x0=1; 确性，还必须证明 c-=wfi]; 背包问题具有贪心 } 选择性质。 if (i<=n)x[i]=c/ti]; 背包问题的贪心选择性质证明见文献王晓东，傅清祥，叶东毅， 算法与数据结构学习指导与习题解析，P68-70。电子工业出版社， 2025年4月3日 2000.] 14
2025年4月3日 14 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; } 算法knapsack 的主要计算时间在 于将各种物品依其 单位重量的价值从 大到小排序。因此， 算法的计算时间上 界为 O（nlogn）。 为了证明算法的正 确性，还必须证明 背包问题具有贪心 选择性质。 1.5 0-1背包问题和背包问题 背包问题的贪心选择性质证明见文献[王晓东，傅清祥，叶东毅， 算法与数据结构学习指导与习题解析，P68-70。电子工业出版社， 2000.]
山东程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 对于0-1背包问题，贪心选择之所以不能得到最优解是因 为在这种情况下，它无法保证最终能将背包装满，部分闲 置的背包空间使每公斤背包空间的价值降低了。事实上， 在考虑0-1背包问题时，应比较选择该物品和不选择该物 品所导致的最终方案，然后再作出最好选择。由此就导出 许多互相重叠的子问题。这正是该问题可用动态规划算法 求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0 1背包问题。 2025年4月3日 15
2025年4月3日 15 对于0-1背包问题，贪心选择之所以不能得到最优解是因 为在这种情况下，它无法保证最终能将背包装满，部分闲 置的背包空间使每公斤背包空间的价值降低了。事实上， 在考虑0-1背包问题时，应比较选择该物品和不选择该物 品所导致的最终方案，然后再作出最好选择。由此就导出 许多互相重叠的子问题。这正是该问题可用动态规划算法 求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0- 1背包问题