在0 / 1背包问题中，需对容量为c的背包举办装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，代价为pi。对付可行的背包装载，背包中物品的总重量不能高出背包的容量，最佳装载是指所装入的物品代价最高，即n ?i=1pi xi 取得最大值。约束条件为n ?i=1wi xi≤c 和xi?[0 , 1]( 1≤i≤n)。
在这个表达式中，需求出xt的值。xi=1暗示物品i 装入背包中，xi=0 暗示物品i 不装入背包。0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所得到的代价差异。货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。 例1-8 在杂货店角逐中你得到了第一名，奖品是一车免费杂货。店中有n 种差异的货品。法则划定从每种货品中最多只能拿一件，车子的容量为c，物品i 需占用wi的空间，代价为pi。你的方针是使车中装载的物品代价最大。虽然，所装货品不能高出车的容量，且同一种物品不得拿走多件。这个问题可模拟0 / 1背包问题举办建模，个中车对应于背包，货品对应于物品。
0 / 1背包问题有好几种贪婪计策，每个贪婪计策都回收多步进程来完成背包的装入。在每一步进程中操作贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的代价最大的物品，操作这种法则，代价最大的物品首先被装入（假设有足够容量），然后是下一个代价最大的物品，如此继承下去。这种计策不能担保获得最优解。譬喻，思量n=2, w=[100,10,10], p=[20,15,15], c=1 0 5。当操作代价贪婪准则时，得到的解为x=[1 , 0 , 0]，这种方案的总代价为2 0。而最优解为[0 , 1 , 1]，其总代价为3 0。
另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。固然这种法则对付前面的例子能发生最优解，但在一般环境下则不必然能获得最优解。思量n=2 ,w=[10,20], p=[5,100], c=2 5。当操作重量贪婪计策时，得到的解为x=[1,0], 比最优解[0 , 1]要差。
还可以操作另一方案，代价密度pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可
装入包的pi /wi 值最大的物品，这种计策也不能担保获得最优解。操作此计策试解n=3 ,w=[20,15,15], p=[40,25,25], 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)时间内得到如此好的机能。我们也许会问，是否存在一个x(x<1 0 0)，使得贪婪开导法的功效与最优值相差在x%以内。谜底是否认的。为说明这一点，思量例子n=2, w=[1 ,y], p=[1 0 , 9y], 和c=y。贪婪算法功效为x=[1,0], 这种方案的值为1 0。对付y≥1 0 / 9，最优解的值为9 y。因此，贪婪算法的值与最优解的差对最优解的比例为(( 9y – 1 0)/9y* 1 0 0) %，对付大的y，这个值趋近于1 0 0 %。可是可以成立贪婪开导式要领来提供解，使解的功效与最优解的值之差在最优值的x%(x<100) 之内。首先将最多k 件物品放入背包，假如这k 件物品重量大于c，则放弃它。不然，剩余的容量用来思量将剩余物品按pi /wi 递减的顺序装入。通过思量由开导法发生的解法中最多为k 件物品的所有大概的子集来获得最优解。
例13-9 思量n=4, w=[2,4,6,7], 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的贪婪开导式算法获得的。
#p#分页标题#e#
若k=2，除了思量k< 2的子集，还必须思量子集{1 , 2} , {1 , 3} , {1 , 4} , {2 , 3} , {2 , 4}和{3 , 4}。首先从最后一个子集开始，它是不行行的，故将其丢弃，剩下的子集经求解别离获得如下功效：[1 , 1 , 0 , 0] , [1 , 0 , 1 , 0] , [1 , 0 , 0 , 1] , [0 , 1 , 1 , 0]和[0 , 1 , 0 , 1]，这些功效中最后一个代价为2 3，它的值比k=0和k=1时得到的解要高，这个谜底即为开导式要领发生的功效。 这种修改后的贪婪开导要领称为k阶优化要领（k – o p t i m a l）。也就是，若从谜底中取出k 件物品，并放入别的k 件，得到的功效不会比本来的好，并且用这种方法得到的值在最优值的( 1 0 0 /(k + 1)) %以内。当k=1时，担保最终功效在最佳值的5 0 %以内；当k=2时，则在3 3 . 3 3 %以内等等，这种开导式要领的执行时间随k的增大而增加，需要测试的子集数目为O(nk)，每一个子集所需时间为O(n)，因此当k >0时总的时间开销为O(nk+1)。实际调查到的机能要好得多。
