0/1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入，在每一步过程中利用贪婪准则选择一个物品装入背包。
1、从剩余的物品中，选出可以装入背包的价值最大的物品。利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，n=2, weight=[100, 10, 10], prize=[20, 15, 15], count=105。当利用价值贪婪准则时，获得的解为x= [1, 0, 0]，这种方案的总价值为20。而最优解为[0, 1, 1]，其总价值为30。
2、重量贪婪准则：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n=2 ,w=[10,20], p=[5,100], c=25。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[0, 1]要差。
3、还可以利用另一方案，价值密度pi/wi 贪婪算法，这种选择准则为：从剩余物品中选择可装入包的pi/wi值最大的物品。这种策略也不能保证得到最优解，利用此策略试解n=3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。
我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧，0/1背包问题是一个NP-复杂问题，对于这类问题，也许根本就不可能找到具有多项式时间的算法。虽然按pi/wi非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数时候能很好地接近最后算法。在600个随机产生的背包问题中，用这种启发式贪婪算法来解有239题为最优解。有583个例子与最优解相差10%，所有600个答案与最优解之差全在25%以内。该算法能在O(nlogn)时间内获得如此好的性能。我们也许会问，是否存在一个x(x<100)，使得贪婪启发法的结果与最优值相差在x%以内？答案是否定的。考虑例子n=2,w=[1,y],p=[10,9y],c=y。贪婪算法结果为x=[1,0], 这种方案的值为10。对于y≥10/9，最优解的值为9y。因此，贪婪算法的值与最优解的差对最优解的比例为((9y-10)/9y*100)%，对于大的y，这个值趋近于100%。
可以建立贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优值的x%(x<100)之内。首先将最多k件物品放入背包，假如这k件物品重量大于c，则放弃它。否则，剩余的容量用来考虑将剩余物品按pi/wi递减的顺序装入。通过考虑由启发法产生的解法中最多为k件物品的所有可能的子集来得到最优解。
例：考虑n=4, w=[2,4,6,7], p=[6,10,12,13], c=11。
当k=0时，背包直接按物品价值密度非递减顺序装入，首先将物品1放入背包，然后是物品2，背包剩下的容量为5个单元，剩下的物品没有一个合适的，因此解为x=[1,1,0,0]。此解获得的价值为16。
现在考虑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]，获得的价值为18。若从子集{4}开始，产生的解为x = [1,0,0,1]，获得的价值为19。考虑k为0和1时获得的最优解为[1,0,0,1]。这个解是通过k=1的贪婪启发式算法得到的。
若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]，这些结果中最后一个价值为23，它的值比k=0和k=1时获得的解要高，这个答案即为启发式方法产生的结果。
这种修改后的贪婪启发方法称为k阶优化方法（k-optimal）。也就是，若从答案中取出k件物品，并放入另外k件，获得的结果不会比原来的好，而且用这种方式获得的值在最优值的(100/(k+1))%以内。当k= 1时，保证最终结果在最佳值的50%以内；当k=2时，则在33.33%以内等等，这种启发式方法的执行时间随k的增大而增加，需要测试的子集数目为O(nk)，每一个子集所需时间为O(n)，因此当k>0时总的时间开销为O (nk+1)。实际观察到的性能要好得多。
PS:
背包是np完全问题。网上还有动态规划算法:
f(i, x) = max{f(i-1, x-W[i]) + C[i], f(i-1, x)} 最终解f(n, p)。
还有分支限界法，感觉跟递归没区别。
甚至还有遗传算法……