c 语言算法--贪婪算法0/1 背包问题 在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的 重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指 所装入的物品价值最高WhatsApp网页版，即n ?i=1pi xi 取得最大值。约束条件为n ?i =1wi xi≤c 和xi? ( 1≤i≤n)。在这个表达式中，需求出xt 的值。xi = 1 表示物品i 装入背包中，xi =0 表示物品i 不装入背包。 0 / 1 背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。货箱装载问题转化为背包 问题的形式为：船作为背包WhatsApp网页版，货箱作为可装入背包的物品。 例 1-8 在杂货店比赛中你获得了第一名，奖 品是一车免费杂货。店中有n 种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为c， 物品i 需占用wi 的空间，价值为pi 。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过 车的容量，且同一种物品不得拿走多件。这个问题可仿照0 / 1 背包问题进行建模，其中车对应于背包， 货物对应于物品。0 / 1 背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程 中利用贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最 大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物 品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=
100,10,10
, p =, c = 1 0 5。当利用价值贪婪准则时，获得的解为x= ，这种方案的总价值为2 0。而最优解 为，其总价值为3 0。另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对 于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=, p=, c= 2 5。当利用重量贪婪策略时，获得的解为x =, 比最优解要差。还可以利用另一方案，价值密度pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可装入包的pi /wi 值最大的物品，这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=, p=, c=30 时的最优解。我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧， 0 / 1背包问题是一个N P-复杂问 题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。虽然按pi /wi 非递（增）减的次序装 入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数 时候能很好地接近最后算法。在6 0 0 个随机产生的背包问题中，用这种启发式贪婪算法来解有2 3 9 题 为最优解。有5 8 3 个例子与最优解相差 1 0 %，所有6 0 0 个答案与最优解之差全在2 5 %以内。该 算法能在O (nl o gn)时间内获得如此好的性能。我们也许会问WhatsApp网页版，是否存在一个x (x1 0 0 )，使得贪婪 启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点，考虑例子n =2, w = , p= , 和c= y。贪婪算法结果为x=, 这种方案的值为 1 0。对于y≥1 0 / 9，最优解的值为 9 y。因此，贪婪算法的值与最优解的差对最优解的比例为( ( 9y - 1 0)/9y* 1 0 0 ) %，对于大的y， 这个值趋近于 1 0 0 %。但是可以建立贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优值 的x% (x100) 之内。首先将最多k 件物品放入背包，如果这k 件物品重量大于c，则放弃它。否则， 剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序装入。通过考虑由启发法产生的解法中最多为k 件 物品的所有可能的子集来得到最优解。例 13-9 考虑n =4, w=, p=
6,10,12,13
, c = 11。当k= 0 时，背包按物品价值密度 非递减顺序装入，首先将物品 1 放入背包，然后是物品2，背包剩下的容量为5 个单元，剩下的物品没有 一个合适的，因此解为x =
1 , 1 , 0 , 0
。此解获得的价值为1 6。现在考虑k = 1 时的贪婪启发法。最初的子集为{ 1 } , { 2 } , { 3 } , { 4 }。子集{ 1 } , { 2 } 产生与k= 0 时相同的结果，考虑子集{ 3 }，置x3 为1。此时还剩5 个单位的容量，按价值密度非递增 顺序来考虑如何利用这5 个单位的容量。首先考虑物品 1，它适合，因此取x1 为1，这时仅剩下3 个单 位容量了，且剩余物品没有能够加入背包中的物品。通过子集{ 3 }开始求解得结果为x =
1 , 0 , 1 , 0
， 获得的价值为 1 8。若从子集{ 4 }开始，产生的解为x =
1 , 0 , 0 , 1
，获得的价值为1 9。考虑子 集大小为0 和 1 时获得的最优解为
1 , 0 , 0 , 1
。这个解是通过k= 1