m[n][c]为最优值，如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都一样，则x[n]=0 ; 否则 x[n]=1 。当x[n]=0时，由x[n-1][c]继续构造最优解；当x[n]=1时，则由x[n-1][c-w[i]]继续构造最优解 。以此类推，可构造出所有的最优解 。
void traceback(){for(int i=n;i>1;i--){if(m[i][c]==m[i-1][c])x[i]=0;else{x[i]=1;c-=w[i];}}x[1]=(m[1][c]>0)?1:0;}
参考链接：总结——01背包问题 （动态规划算法）
1、为什么贪心算法不适于解0/ 1背包问题？
0/1背包问题有好几种贪婪策略，每种贪婪策略都要多个步骤来完成，每一步都利用贪婪准则选择一个物品装入背包 。
一种价值贪婪准则为:从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入(假设有足够容量)，然后是下一个价值最大的物品，如此继续下去 。这种策略不能保证得到最优解 。例如，考虑n= 2w=[10010,10]，p=[2015,15]，c=105当利用价值贪婪准则时，获得的解为x=[ 1, 0，0]，这种方案的总价值为20 。而最优解为[ 0，1, 1]，其总价值为30 。
另一种方案是重量贪婪准则: 从剩下的物品中选择可装入背包的重量最小的物品 。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解 。考虑n=2,w=[1020]，p=[,5100]，c=25当利用重量贪婪策略时，获得的解为x=[,10],比最优解[01]要差 。还可以利用另一方案，价值密度p; / w贪婪算法，这种选择准则为:从剩余物品中选择可装入包的p; / w值最大的物品，这种策略也不能保证得到最优解 。
2、贪心算法适用于部分背包问题
这里适用于可拆分的物品，部分背包问题可以用贪心算法求解，且能够得到最优解 。
贪心策略：将物品按单位重量所具有的价值比排序，总是优先选择单位重量下价值最大的物品 。
所以我们可以通过求出所有物品的性价比并排序，然后从性价比最大的开始选择，尽可能多拿该物品，直到装满为止 。
部分背包问题可以用贪心算法求解，且能够得到最优解 。
贪心策略是什么呢？将物品按单位重量所具有的价值排序 。总是优先选择单位重量下价值最大的物品 。
单位重量所具有的价值：Vi / Wi
举个例子：假设背包可容纳50Kg的重量，物品信息如下：
物品 i 重量(Kg) 价值 单位重量的价值
1 10 60 6
2 20 100 5
3 30 120 4
按照我们的贪心策略，单位重量的价值排序： 物品1 > 物品2 > 物品3
因此，我们尽可能地多拿物品1，直到将物品1拿完之后，才去拿物品2.....
最终贪心选择的结果是这样的：物品1全部拿完，物品2也全部拿完，物品3拿走10Kg（只拿走了物品3的一部分！！！），这种选择获得的价值是最大的 。
而对于0-1背包问题，如果也按“优先选择单位重量下价值最大的物品”这个贪心策略，那么，在拿了物品1和物品2之后，就不能在拿物品3了 。因为，在拿了物品1和物品2之后，背包中已经装了10+20=30Kg的物品了，已经装不下物品3了（50-30 < 30）（0-1背包：一件物品要么拿，要么不拿，否能只拿一部分）,此时得到的总价值是 160 。而如果拿物品2和物品3，得到的价值为220 。这说明，该贪心策略对0-1背包问题，不能求得最优解 。这时如果想得到全部的最优解，我们就要用到动态规划解决这一题 。
C++代码：
/** 贪心算法解决部分背包问题:用每个物品价值除以重量然后按照从大到小的顺序依次装入，直至背包装满 。**/using namespace std;/*排序函数，将物品按照从大到小排序（价值/重量）*/void swap (float ave[], int s[], int n){int i, j;for (i = 0; i