（ 1 ）贪心算法 O （ nlog （ n ）） Ø 首先计算每种物品单位重量的价值 Vi/Wi ，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过 C ，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 Ø 具体算法可描述如下： 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]; } （ 2 ）动态规划法 O(nc) m(i ， j) 是背包容量为 j ，可选择物品为 i ， i+1 ， … ， n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性质，可以建立计算 m(i ， j) 的递归式如下。 void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c); for (j=0;j<=jMax;j++) /*m(n,j)=0 0==w[n]*/ m[n][j]=v[n]; for (i=n-1;i>1;i--) { int jMax=min(w[i]-1,c); for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0==w[n]*/ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } （ 3 ）回溯法 O(2 n ) cw: 当前重量 cp: 当前价值 bestp ：当前最优值 void backtrack(int i) // 回溯法 i 初值 1 {    if(i > n) // 到达叶结点 { bestp = cp;              return;            } if(cw + w[i] <= c) // 搜索左子树 { cw += w[i]; cp += p[i]; backtrack(i+1); cw -= w[i]; cp -= p[i]; } if(Bound(i+1)>bestp) // 搜索右子树 backtrack(i+1); }