分别用贪心算法、动态规划法、回溯法设计 0-1 背包

（ 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)

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=<j<w[n]*/

m[n][j]=0;

for (j=w[n];j<=c;j++) /*m(n,j)=v[n] j>=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=<j<w[i]*/

m[i][j]=m[i+1][j];

for (j=w[i];j<=c;j++)/*m(n,j)=v[n] j>=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 ⁿ )

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);

}